結果
問題 | No.363 門松サイクル |
ユーザー | rickytheta |
提出日時 | 2016-04-19 00:05:54 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 219 ms / 4,000 ms |
コード長 | 2,978 bytes |
コンパイル時間 | 2,257 ms |
コンパイル使用メモリ | 151,668 KB |
実行使用メモリ | 30,480 KB |
最終ジャッジ日時 | 2023-07-27 16:24:15 |
合計ジャッジ時間 | 6,761 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
10,148 KB |
testcase_01 | AC | 3 ms
10,032 KB |
testcase_02 | AC | 5 ms
10,188 KB |
testcase_03 | AC | 4 ms
10,240 KB |
testcase_04 | AC | 4 ms
10,148 KB |
testcase_05 | AC | 5 ms
10,072 KB |
testcase_06 | AC | 5 ms
10,060 KB |
testcase_07 | AC | 5 ms
10,324 KB |
testcase_08 | AC | 5 ms
10,136 KB |
testcase_09 | AC | 72 ms
19,880 KB |
testcase_10 | AC | 65 ms
19,956 KB |
testcase_11 | AC | 154 ms
29,936 KB |
testcase_12 | AC | 180 ms
29,660 KB |
testcase_13 | AC | 141 ms
29,724 KB |
testcase_14 | AC | 109 ms
27,472 KB |
testcase_15 | AC | 130 ms
29,728 KB |
testcase_16 | AC | 126 ms
24,368 KB |
testcase_17 | AC | 209 ms
29,916 KB |
testcase_18 | AC | 165 ms
29,940 KB |
testcase_19 | AC | 119 ms
30,480 KB |
testcase_20 | AC | 166 ms
29,952 KB |
testcase_21 | AC | 219 ms
29,912 KB |
testcase_22 | AC | 156 ms
30,016 KB |
testcase_23 | AC | 206 ms
27,344 KB |
testcase_24 | AC | 4 ms
10,040 KB |
testcase_25 | AC | 4 ms
10,048 KB |
testcase_26 | AC | 127 ms
29,912 KB |
testcase_27 | AC | 128 ms
29,856 KB |
testcase_28 | AC | 173 ms
29,856 KB |
ソースコード
// 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; }