結果
問題 | No.363 門松サイクル |
ユーザー | char134217728 |
提出日時 | 2018-01-04 04:47:34 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 160 ms / 4,000 ms |
コード長 | 3,521 bytes |
コンパイル時間 | 2,284 ms |
コンパイル使用メモリ | 210,888 KB |
実行使用メモリ | 19,072 KB |
最終ジャッジ日時 | 2024-06-02 07:50:21 |
合計ジャッジ時間 | 7,717 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,632 KB |
testcase_01 | AC | 3 ms
5,888 KB |
testcase_02 | AC | 5 ms
6,016 KB |
testcase_03 | AC | 4 ms
6,016 KB |
testcase_04 | AC | 4 ms
5,888 KB |
testcase_05 | AC | 5 ms
6,016 KB |
testcase_06 | AC | 4 ms
5,888 KB |
testcase_07 | AC | 4 ms
5,888 KB |
testcase_08 | AC | 5 ms
5,760 KB |
testcase_09 | AC | 53 ms
11,776 KB |
testcase_10 | AC | 57 ms
12,288 KB |
testcase_11 | AC | 119 ms
18,416 KB |
testcase_12 | AC | 132 ms
17,280 KB |
testcase_13 | AC | 124 ms
17,408 KB |
testcase_14 | AC | 103 ms
16,384 KB |
testcase_15 | AC | 99 ms
17,664 KB |
testcase_16 | AC | 78 ms
13,440 KB |
testcase_17 | AC | 160 ms
18,688 KB |
testcase_18 | AC | 144 ms
18,432 KB |
testcase_19 | AC | 122 ms
19,072 KB |
testcase_20 | AC | 147 ms
18,560 KB |
testcase_21 | AC | 154 ms
18,560 KB |
testcase_22 | AC | 122 ms
18,304 KB |
testcase_23 | AC | 118 ms
16,128 KB |
testcase_24 | AC | 4 ms
5,760 KB |
testcase_25 | AC | 4 ms
5,760 KB |
testcase_26 | AC | 112 ms
18,432 KB |
testcase_27 | AC | 105 ms
18,484 KB |
testcase_28 | AC | 142 ms
18,432 KB |
コンパイルメッセージ
main.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 93 | main(){ | ^~~~
ソースコード
#include <bits/stdc++.h> #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define FORR(i,a,b) for (int i=(a);i>=(b);i--) #define pb push_back #define pcnt __builtin_popcount #define show(x) cout<<#x<<" = "<<x<<endl; #define maxs(x,y) x = max(x,y) #define mins(x,y) x = min(x,y) #define fi first #define se second #define rng(a) (a.begin()),(a.end()) #define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++) #define sz(x) (int)(x).size() #define mp make_pair using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<pii> vpii; typedef set<int> si; typedef pair<ll,ll> pll; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<pll> vpll; typedef set<ll> sl; typedef __int128_t lll; typedef pair<lll,lll> plll; typedef vector<lll> vlll; template<typename T>string join(vector<T>&v) {stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);} ll gcd(ll a,ll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;} int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;} void dout(double d){printf("%.12f\n",d);} const int iinf = 1e9; const ll linf = 1e18; const int mod = 1e9+7; const double pi = acos(-1); const double eps = 1e-10; const int N = 1e5+1; int n, q, A[N], D[N], P[N][18]; bool K[N][18], Y[N]; vi V[N]; bool kdmt(int a, int b, int c){ return (a!=c) && (b < a && b < c || a < b && c < b); } int back(int a, int b){ FOR(i, 0, 18) if(b&(1<<i)) a = P[a][i]; return a; } int _parent(int a, int b){ FORR(i, 17, 0) if(P[a][i] != P[b][i]) return _parent(P[a][i], P[b][i]); return P[a][0]; } int parent(int a, int b){ if(D[a] > D[b]) swap(a, b); b = back(b, D[b]-D[a]); if(a == b) return a; return _parent(a, back(b, D[b]-D[a])); } bool kdmtl(int a, int b){ if(b < 1) return true; FOR(i, 0, 18) if(b&(1<<i)){ if(!K[a][i]) return false; a = P[a][i]; } return true; } bool kdmtc(int a, int b){ if(a == b) return false; if(D[a] > D[b]) swap(a, b); int p = parent(a, b), _a, _b; if(!kdmtl(a, D[a] - D[p] - 1)) return false; if(!kdmtl(b, D[b] - D[p] - 1)) return false; if(a == p){ _a = back(b, D[b] - D[p] - 1); if(!kdmt(A[_a], A[a], A[b])) return false; if(!kdmt(A[a], A[b], A[P[b][0]])) return false; }else{ _a = back(a, D[a] - D[p] - 1); _b = back(b, D[b] - D[p] - 1); if(!kdmt(A[_a], A[p], A[_b])) return false; if(!kdmt(A[P[a][0]], A[a], A[b])) return false; if(!kdmt(A[a], A[b], A[P[b][0]])) return false; } return true; } main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> n; FOR(i, 1, n+1) cin >> A[i]; { int x, y; FOR(i, 0, n-1){ cin >> x >> y; V[x].pb(y); V[y].pb(x); } } { queue<int> q[2]; q[0].push(1); Y[1] = true; P[1][0] = 0; int t, d = 1, i = 0; while(!q[i].empty()){ while(!q[i].empty()){ t = q[i].front(); q[i].pop(); D[t] = d; each(itr, V[t]) if(!Y[*itr]){ Y[*itr] = true; P[*itr][0] = t; q[1-i].push(*itr); } } i = 1 - i; d++; } FOR(i, 1, 18)FOR(j, 0, n+1) P[j][i] = P[P[j][i-1]][i-1]; } FOR(i, 0, n+1) if(D[i] > 2) K[i][0] = kdmt(A[i], A[P[i][0]], A[P[i][1]]); FOR(j, 1, 18) FOR(i, 0, n+1) K[i][j] = K[i][j-1] && K[P[i][j-1]][j-1]; cin >> q; { int u, v; FOR(i, 0, q){ cin >> u >> v; cout << (kdmtc(u, v) ? "YES\n" : "NO\n"); } } return 0; }