一条拉拉拉拉完了的拉拉区的游记

· · 生活·游记

Day 0

从学校直接去日照,进行神秘试机写出无 lazytag 的线段树并面基了一堆人。晚上吃了星程的面,好吃喵~

Day 1

早上看看往年的题并对着一些同学犯花痴(逃

中午吃了两个汉堡并依据前 3 年的惯例背一遍 dijkstra(上次有亲爱的 @Central_GYM 同学提醒我 Kruskal(逃(总之我应该是和 T2 的算法有缘(

去考场,进行一些久违的拍照,到机房。

@Maggie114514发现上午小朋友把编译器背景颜色改成滚木,故帮忙改回去,望 rp++(

开题

为啥 T2 题面这么长(史(

T1

啥子二分,神秘前缀和,30min 过掉(其中 20min)是因为读错题了(

T2

进行一些 Dijkstra 的暴力(直接建图跑)

1h 后发现可以把点压成边,故进行神秘改图(我不喜欢重构导致)

又过了 1h

遂发现时间复杂度过高进行去重操作

                if(e[v][j]<=Ztsj||e[v][j]==u+Ztsj)continue;
                ne[u].push_back(e[v][j]-Ztsj);
                nw[u].push_back(w[u+Ztsj][i]+w[v][j]);

可以看出改图算法非常的史

随后发现样例卡 5s 于是进行一定的代码精简,并使用 namespace 进行特殊性质的打 进行 30min

开 T3&T4

但是实际上写了一坨答辩获得 0pts 故不进行展示

浪费 30min

回到 T2

最后发现我是啥子特殊性质用主要代码能过,于是进行删除,并优化代码 30min

考试结束

但是其实我是啥子,因为 T3 我也读错题了,并且我的啥子 T2 令我十分慌张

和同学互相制造焦虑

进行返程并大吃羊汤

Day 114514

发现自己就是个啥子

因为这是我考场交的 T2 代码:

::::info[一只啥子非要 q 一遍跑一边]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=505,M=5e5+505,inf=1e18,Ztsj=5e5;
int c,n,m,d,q,k;

namespace dijkpro{
    int a[M],u,v;
    vector<int> e[M],w[M],ne[N],nw[N];
    int dis[N];
    void find(int u){
        int v=0;
        for(int i=0;i<e[u+Ztsj].size();i++){
            v=e[u+Ztsj][i];
            if(v>Ztsj)continue;
            for(int j=0;j<e[v].size();j++){
                if(e[v][j]<=Ztsj||e[v][j]==u+Ztsj)continue;
                ne[u].push_back(e[v][j]-Ztsj);
                nw[u].push_back(w[u+Ztsj][i]+w[v][j]);
            }
        }
    }
    void initall(){
        for(int i=0;i<N;i++)dis[i]=inf;
    }
    struct node{
        int dis,pos;
        bool operator <(const node nd)const{
            return dis>nd.dis;
        }
    };
    priority_queue<node> pq;
    void dijkstra(int s){
        int u,v;
        initall();
        pq.push({0,s});
        dis[s]=0;
        while(pq.size()){
            u=pq.top().pos;
            pq.pop();
            int di=dis[u];
            for(int i=0;i<ne[u].size();i++){
                v=ne[u][i];
                if(dis[v]>dis[u]+nw[u][i]){
                    dis[v]=dis[u]+nw[u][i];
                    pq.push({dis[v],v});
                }
            }
        }
        return;
    }
    int query(int x,int y){
        int res=inf;
        for(int i=0;i<e[x].size();i++){
            if(e[x][i]<=Ztsj)continue;
            dijkstra(e[x][i]-Ztsj);
            for(int j=0;j<e[y].size();j++){
                if(e[y][j]<=Ztsj)continue;
                res=min(res,w[x][i]+dis[e[y][j]-Ztsj]+w[y][j]);
            }
        }
        return res+a[x]+a[y];
    }
    void solve(){
        for(int i=1;i<=m;i++)cin>>a[i];
        for(int i=1;i<=n;i++){
            cin>>k;
            for(int j=1;j<=k;j++){
                cin>>u>>v;
                e[i+Ztsj].push_back(u);
                w[i+Ztsj].push_back(v);
                e[u].push_back(i+Ztsj);
                w[u].push_back(v);
            }
        }
        for(int i=1;i<=n;i++)find(i);

//      for(int i=1;i<=n;i++){
//          for(int j=0;j<ne[i].size();j++)cout<<ne[i][j]<<' '<<nw[i][j]<<'|';
//          cout<<'\n';
//      }

        for(int i=1;i<=q;i++){
            int x,y;
            cin>>x>>y;
            cout<<query(x,y)<<'\n';
        } 
    }
}

signed main(){
    freopen("subway.in","r",stdin);
    freopen("subway.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>c>>n>>m>>d>>q;
    dijkpro::solve();
    return 0;
}
/*

luogu user 667452 hu guan pls

<shi mo ge zhe>

wo yi ran zai wu ren wen jin de yin yu mei shi zhi di
he zhe yu yin chang zhe mei you ting zhong de ge qu
ren chao reng shi man wu mu di de xiang mu di di san qu
mang lu zhe wu wei zhe ji xu

qi qiu zhe shui neng gou jiang wo de xin fang qing qing kou ji
ji shi shi ni ye jin jin zhu zu le pian ke bian li qu
xiang zhe huo xu xia ge lu kou hui you shui yu wo xiang yu
na pa zhi yi shun de qi ji

<dong jing bu tai re>

ding ding dang dang QQ xiang qi hui shi shui ne Nayo
hui shi ta ma Nayo
shen me shi ne Ayo

jia zhuang zheng jing bang ta ba shi qing dou bai ping Nayo
bu duo liao le Nayo
qu chi fan le Ayo

xin li ming ming hen xi huan que bao chi zhe ju li
o pa bei shang hai jiu wei zhuang chu gao leng de biao qing
yi wei zhe yang zong you yi tian ta hui jie jin ni
zhi dao na tian kan jian ta he bie ren zai yi qi

��֮���ͻ��˰�

���CSPҲ��û���ˣ�T2�������������T3�����Բ���һ�㣬Ȼ��T4����û���꣬T1��ȷ�Դ��� 

T2 ��� ������5��������ˣ����ⳣ��������һ�㰡�� 

*/


::::

而这时可以过的代码:

::::info[提前 dijkstra 好]

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=505,M=5e5+505,inf=1e18,Ztsj=5e5;
int c,n,m,d,q,k;

namespace dijkpro{
    int a[M],u,v;
    vector<int> e[M],w[M],ne[N],nw[N];
    int dis[N][N];
    void find(int u){
        int v=0;
        for(int i=0;i<e[u+Ztsj].size();i++){
            v=e[u+Ztsj][i];
            if(v>Ztsj)continue;
            for(int j=0;j<e[v].size();j++){
                if(e[v][j]<=Ztsj||e[v][j]==u+Ztsj)continue;
                ne[u].push_back(e[v][j]-Ztsj);
                nw[u].push_back(w[u+Ztsj][i]+w[v][j]);
            }
        }
    }
    void initall(int x){
        for(int i=0;i<N;i++)dis[x][i]=inf;
    }
    struct node{
        int dis,pos;
        bool operator <(const node nd)const{
            return dis>nd.dis;
        }
    };
    priority_queue<node> pq;
    void dijkstra(int s){
        int u,v;
        initall(s);
        pq.push({0,s});
        dis[s][s]=0;
        while(pq.size()){
            u=pq.top().pos;
            pq.pop();
            int di=dis[s][u];
            for(int i=0;i<ne[u].size();i++){
                v=ne[u][i];
                if(dis[s][v]>dis[s][u]+nw[u][i]){
                    dis[s][v]=dis[s][u]+nw[u][i];
                    pq.push({dis[s][v],v});
                }
            }
        }
        return;
    }
    int query(int x,int y){
        int res=inf;
        for(int i=0;i<e[x].size();i++){
            if(e[x][i]<=Ztsj)continue;
            for(int j=0;j<e[y].size();j++){
                if(e[y][j]<=Ztsj)continue;
                res=min(res,w[x][i]+dis[e[x][i]-Ztsj][e[y][j]-Ztsj]+w[y][j]);
            }
        }
        return res+a[x]+a[y];
    }
    void solve(){
        for(int i=1;i<=m;i++)cin>>a[i];
        for(int i=1;i<=n;i++){
            cin>>k;
            for(int j=1;j<=k;j++){
                cin>>u>>v;
                e[i+Ztsj].push_back(u);
                w[i+Ztsj].push_back(v);
                e[u].push_back(i+Ztsj);
                w[u].push_back(v);
            }
        }
        for(int i=1;i<=n;i++)find(i);
        for(int i=1;i<=n;i++)dijkstra(i);

//      for(int i=1;i<=n;i++){
//          for(int j=0;j<ne[i].size();j++)cout<<ne[i][j]<<' '<<nw[i][j]<<'|';
//          cout<<'\n';
//      }

        for(int i=1;i<=q;i++){
            int x,y;
            cin>>x>>y;
            cout<<query(x,y)<<'\n';
        } 
    }
}

signed main(){
    freopen("subway.in","r",stdin);
    freopen("subway.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>c>>n>>m>>d>>q;
    dijkpro::solve();
    return 0;
}
/*

luogu user 667452 hu guan pls

<shi mo ge zhe>

wo yi ran zai wu ren wen jin de yin yu mei shi zhi di
he zhe yu yin chang zhe mei you ting zhong de ge qu
ren chao reng shi man wu mu di de xiang mu di di san qu
mang lu zhe wu wei zhe ji xu

qi qiu zhe shui neng gou jiang wo de xin fang qing qing kou ji
ji shi shi ni ye jin jin zhu zu le pian ke bian li qu
xiang zhe huo xu xia ge lu kou hui you shui yu wo xiang yu
na pa zhi yi shun de qi ji

<dong jing bu tai re>

ding ding dang dang QQ xiang qi hui shi shui ne Nayo
hui shi ta ma Nayo
shen me shi ne Ayo

jia zhuang zheng jing bang ta ba shi qing dou bai ping Nayo
bu duo liao le Nayo
qu chi fan le Ayo

xin li ming ming hen xi huan que bao chi zhe ju li
o pa bei shang hai jiu wei zhuang chu gao leng de biao qing
yi wei zhe yang zong you yi tian ta hui jie jin ni
zhi dao na tian kan jian ta he bie ren zai yi qi

��֮���ͻ��˰�

���CSPҲ��û���ˣ�T2�������������T3�����Բ���һ�㣬Ȼ��T4����û���꣬T1��ȷ�Դ��� 

T2 ��� ������5��������ˣ����ⳣ��������һ�㰡�� 

*/



::::

故 188pts 遗憾离场并应该会上迷惑行为大赏

结尾

总之,催一下今年的 SD-S 迷惑行为大赏