# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
863291 | 2023-10-20T01:29:31 Z | willychan | Flights (JOI22_flights) | C++17 | 183 ms | 4196 KB |
#include "Ali.h" #include<iostream> #include <string> #include <vector> #include<cassert> #include<queue> #include<algorithm> namespace { std::vector<std::vector<int> > side; int rN = 0; std::vector<int> p[20]; std::vector<int> dep; std::vector<int> dfn; std::vector<int> dfn2ind; int t = 0; std::vector<int> mt2t; std::vector<int> dfmt; int mt = 0; void dfs(int cur){ dfn[cur]=t++; dfmt[cur]=mt++; mt2t.push_back(dfn[cur]); dfn2ind.push_back(cur); for(int i : side[cur]) { if(!dep[i]){ p[0][i]= cur; dep[i]=dep[cur]+1; dfs(i); } } t++; dfn2ind.push_back(p[0][cur]); } int dis(int a,int b){ if(a==b) return 0; if(dep[a]>dep[b]) std::swap(a,b); int oga = a; int ogb = b; for(int i=19;i>=0;i--){ if(dep[p[i][b]]>=dep[a]) b=p[i][b]; } if(a==b) return dep[ogb]-dep[oga]; for(int i=19;i>=0;i--){ if(p[i][a]!=p[i][b]){ a = p[i][a]; b = p[i][b]; } } b = p[0][b]; a = p[0][a]; int c = b; return dep[oga]+dep[ogb]-2*dep[c]; } std::string dtb(int x){ std::string s; for(int i=0;i<14;i++){ if((x>>i)&1) s+='1'; else s+='0'; } return s; } } void Init(int N, std::vector<int> U, std::vector<int> V) { rN=N; side.resize(N); dep.resize(N); dfn.resize(N); dfmt.resize(N); t=0; mt=0; dfn2ind.clear(); mt2t.clear(); for(int i=0;i<20;i++) p[i].resize(N); for(int i=0;i<N;i++){ dfn[i]=0; dep[i]=0; dfmt[i]=0; side[i].clear(); for(int k=0;k<20;k++) p[k][i]=0; } for(int i=0;i<N-1;i++){ side[U[i]].push_back(V[i]); side[V[i]].push_back(U[i]); } dep[0]=1; dfs(0); for(int j=1;j<20;j++) { for(int i=0;i<N;i++) p[j][i] = p[j-1][p[j-1][i]]; } /* for(int i=0;i<N;i++) std::cout<<dfmt[i]<<" "; std::cout<<'\n'; for(int i=0;i<N;i++) std::cout<<dfn2ind[mt2t[dfmt[i]]]<<" "; std::cout<<'\n'; */ for(int i=0;i<N;i++) SetID(i,dfmt[i]); } std::string SendA(std::string S) { //std::cout<<"ans:"<<dep[2015]<<" "<<dep[3582]<<"\n"; std::string re; int xm = 0; int ym = 0; for(int i=0;i<10;i++){ if(S[i]=='1') xm+=(1<<i); if(S[i+10]=='1') ym+=(1<<i); } std::vector<int> pospos; for(int i=0;i<10;i++){ if(xm+(1024)*i<rN) re+=dtb(dep[dfn2ind[mt2t[xm+(1024)*i]]]); else re+=dtb(0); if(xm+(1024)*i<rN) pospos.push_back(mt2t[xm+(1024)*i]); // if(xm+(1024)*i<rN) std::cout<<xm+(1024)*i<<"->"<<dfn2ind[mt2t[xm+(1024)*i]]<<":"<<dep[dfn2ind[mt2t[xm+(1024)*i]]]<<" "; } // std::cout<<"\n"; for(int i=0;i<10;i++){ if(ym+(1024)*i<rN) re+=dtb(dep[dfn2ind[mt2t[ym+(1024)*i]]]); else re+=dtb(0); if(ym+(1024)*i<rN) pospos.push_back(mt2t[ym+(1024)*i]); // if(ym+(1024)*i<rN) std::cout<<dfn2ind[mt2t[ym+(1024)*i]]<<":"<<dep[dfn2ind[mt2t[ym+(1024)*i]]]<<" "; } // std::cout<<"\n"; std::sort(pospos.begin(),pospos.end()); //for(auto i : dfn) std::cout<<i<<" "; //std::cout<<"\n"; //for(auto i : dfn2ind) std::cout<<i<<" "; //std::cout<<std::endl<<"pospos:"; //for(auto i : pospos) std::cout<<i<<" "; //std::cout<<"\n"; for(int i=0;i<pospos.size()-1;i++){ int minn = 1e9; for(int l=pospos[i];l<=pospos[i+1];l++) { minn = std::min(minn,dep[dfn2ind[l]]); } re+=dtb(minn); } return re; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 844 KB | Output is correct |
2 | Correct | 0 ms | 1016 KB | Output is correct |
3 | Correct | 0 ms | 664 KB | Output is correct |
4 | Correct | 0 ms | 920 KB | Output is correct |
5 | Correct | 0 ms | 664 KB | Output is correct |
6 | Correct | 5 ms | 2796 KB | Output is correct |
7 | Correct | 5 ms | 2968 KB | Output is correct |
8 | Correct | 5 ms | 2968 KB | Output is correct |
9 | Correct | 5 ms | 2912 KB | Output is correct |
10 | Correct | 5 ms | 2996 KB | Output is correct |
11 | Correct | 4 ms | 2676 KB | Output is correct |
12 | Correct | 5 ms | 2984 KB | Output is correct |
13 | Correct | 6 ms | 2812 KB | Output is correct |
14 | Correct | 5 ms | 3264 KB | Output is correct |
15 | Correct | 5 ms | 3644 KB | Output is correct |
16 | Correct | 4 ms | 3000 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Partially correct | 0 ms | 1028 KB | Output is partially correct |
2 | Partially correct | 39 ms | 3548 KB | Output is partially correct |
3 | Partially correct | 2 ms | 1040 KB | Output is partially correct |
4 | Partially correct | 166 ms | 3504 KB | Output is partially correct |
5 | Partially correct | 174 ms | 2964 KB | Output is partially correct |
6 | Partially correct | 163 ms | 3776 KB | Output is partially correct |
7 | Partially correct | 165 ms | 4020 KB | Output is partially correct |
8 | Partially correct | 162 ms | 3012 KB | Output is partially correct |
9 | Partially correct | 157 ms | 3768 KB | Output is partially correct |
10 | Partially correct | 165 ms | 3696 KB | Output is partially correct |
11 | Partially correct | 160 ms | 3740 KB | Output is partially correct |
12 | Partially correct | 22 ms | 2616 KB | Output is partially correct |
13 | Partially correct | 106 ms | 3316 KB | Output is partially correct |
14 | Partially correct | 101 ms | 3164 KB | Output is partially correct |
15 | Partially correct | 3 ms | 1092 KB | Output is partially correct |
16 | Partially correct | 154 ms | 4080 KB | Output is partially correct |
17 | Partially correct | 153 ms | 4196 KB | Output is partially correct |
18 | Partially correct | 162 ms | 3628 KB | Output is partially correct |
19 | Partially correct | 167 ms | 3296 KB | Output is partially correct |
20 | Partially correct | 101 ms | 3412 KB | Output is partially correct |
21 | Partially correct | 145 ms | 3760 KB | Output is partially correct |
22 | Partially correct | 149 ms | 3624 KB | Output is partially correct |
23 | Partially correct | 159 ms | 3180 KB | Output is partially correct |
24 | Partially correct | 153 ms | 3440 KB | Output is partially correct |
25 | Partially correct | 152 ms | 3436 KB | Output is partially correct |
26 | Partially correct | 150 ms | 3472 KB | Output is partially correct |
27 | Partially correct | 164 ms | 3308 KB | Output is partially correct |
28 | Partially correct | 150 ms | 3380 KB | Output is partially correct |
29 | Partially correct | 162 ms | 3568 KB | Output is partially correct |
30 | Partially correct | 155 ms | 2996 KB | Output is partially correct |
31 | Partially correct | 155 ms | 3428 KB | Output is partially correct |
32 | Partially correct | 180 ms | 3456 KB | Output is partially correct |
33 | Partially correct | 154 ms | 3264 KB | Output is partially correct |
34 | Partially correct | 165 ms | 3816 KB | Output is partially correct |
35 | Partially correct | 165 ms | 3544 KB | Output is partially correct |
36 | Partially correct | 183 ms | 3260 KB | Output is partially correct |
37 | Partially correct | 153 ms | 4044 KB | Output is partially correct |
38 | Partially correct | 174 ms | 3736 KB | Output is partially correct |
39 | Partially correct | 26 ms | 3324 KB | Output is partially correct |
40 | Partially correct | 169 ms | 3708 KB | Output is partially correct |