結果
問題 | No.2337 Equidistant |
ユーザー | 111444 |
提出日時 | 2024-10-06 20:39:50 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 428 ms / 4,000 ms |
コード長 | 1,784 bytes |
コンパイル時間 | 1,512 ms |
コンパイル使用メモリ | 172,352 KB |
実行使用メモリ | 51,568 KB |
最終ジャッジ日時 | 2024-10-06 20:40:02 |
合計ジャッジ時間 | 9,207 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
13,660 KB |
testcase_01 | AC | 4 ms
11,672 KB |
testcase_02 | AC | 4 ms
11,260 KB |
testcase_03 | AC | 5 ms
14,348 KB |
testcase_04 | AC | 4 ms
14,256 KB |
testcase_05 | AC | 4 ms
14,576 KB |
testcase_06 | AC | 6 ms
11,428 KB |
testcase_07 | AC | 5 ms
11,840 KB |
testcase_08 | AC | 6 ms
14,204 KB |
testcase_09 | AC | 5 ms
14,128 KB |
testcase_10 | AC | 5 ms
13,144 KB |
testcase_11 | AC | 174 ms
36,304 KB |
testcase_12 | AC | 207 ms
36,076 KB |
testcase_13 | AC | 195 ms
35,968 KB |
testcase_14 | AC | 169 ms
35,392 KB |
testcase_15 | AC | 169 ms
36,392 KB |
testcase_16 | AC | 207 ms
35,380 KB |
testcase_17 | AC | 176 ms
35,956 KB |
testcase_18 | AC | 181 ms
36,408 KB |
testcase_19 | AC | 178 ms
35,804 KB |
testcase_20 | AC | 196 ms
36,184 KB |
testcase_21 | AC | 260 ms
51,568 KB |
testcase_22 | AC | 140 ms
36,324 KB |
testcase_23 | AC | 184 ms
36,212 KB |
testcase_24 | AC | 345 ms
45,984 KB |
testcase_25 | AC | 201 ms
35,328 KB |
testcase_26 | AC | 428 ms
44,672 KB |
testcase_27 | AC | 215 ms
35,200 KB |
testcase_28 | AC | 178 ms
35,072 KB |
ソースコード
bool M1; #define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<" MB\n" #define look_time cerr<<(clock()-Time)*1.0/CLOCKS_PER_SEC<<'\n' #include<bits/stdc++.h> #include<ctime> int _=1; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> PII; #define pb push_back #define fi first #define se second #define rd read() #define Debug(x) (cerr<<x<<endl) inline ll read(){ ll num=0,sign=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-'){sign=-1;}ch=getchar();} while(isdigit(ch)) num=(num<<1)+(num<<3)+ch-'0',ch=getchar(); return num*sign; } const int N=3e5+10; int n,q,dep[N],sz[N],fa[N][20]; vector <int> G[N]; void dfs(int u,int par){ dep[u]=dep[par]+1,fa[u][0]=par,sz[u]=1; for(int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int v:G[u]) if(v^par) dfs(v,u),sz[u]+=sz[v]; } int LCA(int u,int v){ if(dep[u]<dep[v]) swap(u,v); for(int i=19;~i;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i]; if(u==v) return u; for(int i=19;~i;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } int up(int u,int x){ for(int i=19;~i;i--) if(x>>i&1) u=fa[u][i]; return u; } int solve(int u,int v){ if(dep[u]<dep[v]) swap(u,v); int lca=LCA(u,v),t=dep[u]+dep[v]-dep[lca]*2; if(t&1) return 0; else{ if(dep[u]==dep[v]) return n-sz[up(u,(t>>1)-1)]-sz[up(v,(t>>1)-1)]; else return sz[up(u,t>>1)]-sz[up(u,(t>>1)-1)]; } } void Main(){ n=rd,q=rd; for(int i=1,u,v;i<n;i++) u=rd,v=rd,G[u].pb(v),G[v].pb(u); dfs(1,0); while(q--){ int k=2,x=rd,y; if(k==1) printf("%d\n",n); else{ y=rd,printf("%d\n",solve(x,y)); } } } bool M2; signed main(){ // freopen("in.txt","r",stdin); int Time=clock(); look_memory; // _=rd; while(_--) Main(); look_time; } //pay attention to size of array!!!