結果
問題 |
No.363 門松サイクル
|
ユーザー |
![]() |
提出日時 | 2016-04-19 00:05:54 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 161 ms / 4,000 ms |
コード長 | 2,978 bytes |
コンパイル時間 | 1,751 ms |
コンパイル使用メモリ | 165,660 KB |
実行使用メモリ | 30,500 KB |
最終ジャッジ日時 | 2024-10-04 13:59:32 |
合計ジャッジ時間 | 5,310 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:40:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 40 | scanf("%d",&n); | ~~~~~^~~~~~~~~ main.cpp:41:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 41 | REP(i,n)scanf("%d",&a[i]); | ~~~~~^~~~~~~~~~~~ main.cpp:44:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 44 | scanf("%d%d",&x,&y); | ~~~~~^~~~~~~~~~~~~~ main.cpp:79:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 79 | scanf("%d",&q); | ~~~~~^~~~~~~~~ main.cpp:83:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 83 | scanf("%d%d",&s,&t); | ~~~~~^~~~~~~~~~~~~~
ソースコード
// ARC048 D をコピペ #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef complex<double> P; typedef pair<int,int> pii; #define REP(i,n) for(ll i=0;i<n;++i) #define REPR(i,n) for(ll i=1;i<n;++i) #define FOR(i,a,b) for(ll i=a;i<b;++i) #define DEBUG(x) cout<<#x<<": "<<x<<endl #define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl #define ALL(a) (a).begin(),(a).end() #define MOD (ll)(1e9+7) #define ADD(a,b) a=((a)+(b))%MOD #define FIX(a) ((a)%MOD+MOD)%MOD const int INF = 830252521; int n; int a[125252]; vi g[125252]; int depth[125252]; int anc[125252][20]; int query[125252][20]; bool kado(int s,int t,int u){ int x=a[s],y=a[t],z=a[u]; return (x<y&&y>z&&x!=z) || (x>y&&y<z&&x!=z); } int main(){ scanf("%d",&n); REP(i,n)scanf("%d",&a[i]); REP(i,n-1){ int x,y; scanf("%d%d",&x,&y); --x; --y; g[x].push_back(y); g[y].push_back(x); } REP(i,n) depth[i]=INF; REP(i,n)REP(k,20) anc[i][k]=query[i][k]=INF; queue<int> Q; depth[0] = 0; Q.push(0); while(!Q.empty()){ int pos = Q.front(); Q.pop(); int d = depth[pos]; REP(i,g[pos].size()){ int to = g[pos][i]; if(depth[to]!=INF)continue; depth[to] = d+1; Q.push(to); // ダブリング準備 anc[to][0] = pos; query[to][0] = (d+1<2?0:kado(to,pos,anc[pos][0])); int id = 1; int cur = pos; while(anc[cur][id-1]!=INF){ int next = anc[cur][id-1]; anc[to][id] = next; query[to][id] = query[to][id-1] & query[cur][id-1]; cur = next; ++id; } } } int q; scanf("%d",&q); while(q--){ int s,t; scanf("%d%d",&s,&t); --s; --t; if(depth[s]>depth[t])swap(s,t); int x=s, y=t; int diff = depth[y]-depth[x]; REP(k,20){ if(diff&1) y = anc[y][k]; diff>>=1; } REP(_k,20){ int k = 20-1-_k; if(anc[x][k]!=INF && anc[x][k]!=anc[y][k]){ x = anc[x][k]; y = anc[y][k]; } } bool flag = true; if(x!=y){ // s --- x - lca - y --- t int lca = anc[x][0]; flag &= kado(x,lca,y); flag &= kado(anc[s][0],s,t); flag &= kado(anc[t][0],t,s); diff = max(0,depth[s]-depth[lca]-1); x = s; REP(k,20){ if(diff&1){ flag &= query[x][k]; x = anc[x][k]; } diff >>= 1; } diff = max(0,depth[t]-depth[lca]-1); x = t; REP(k,20){ if(diff&1){ flag &= query[x][k]; x = anc[x][k]; } diff >>= 1; } }else{ // s=x=lca=y --- t diff = max(0,depth[t]-depth[s]-1); x = t; REP(k,20){ if(diff&1){ flag &= query[x][k]; x = anc[x][k]; } diff >>= 1; } flag &= kado(x,s,t); flag &= kado(s,t,anc[t][0]); } if(flag)puts("YES"); else puts("NO"); } return 0; }