結果
問題 | No.363 門松サイクル |
ユーザー | ryofjt |
提出日時 | 2016-09-12 20:31:34 |
言語 | C++11 (gcc 11.4.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,519 bytes |
コンパイル時間 | 316 ms |
コンパイル使用メモリ | 51,664 KB |
最終ジャッジ日時 | 2024-11-14 19:49:48 |
合計ジャッジ時間 | 2,991 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:8:9: error: ‘vector’ does not name a type 8 | typedef vector<int> V; | ^~~~~~ main.cpp:13:1: error: ‘V’ does not name a type 13 | V t[100000]; | ^ main.cpp: In function ‘void dfs(int)’: main.cpp:24:20: error: ‘t’ was not declared in this scope 24 | for(int i: t[x]){ | ^ main.cpp: In function ‘int main()’: main.cpp:109:17: error: ‘t’ was not declared in this scope 109 | t[x].push_back(y); | ^ main.cpp:100:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 100 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:102:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 102 | scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:106:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 106 | scanf("%d%d", &x, &y); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:116:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 116 | scanf("%d", &q); | ~~~~~^~~~~~~~~~ main.cpp:119:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 119 | scanf("%d%d", &u, &v); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#include <cstdio> #include <algorithm> #define rep(i, n) for(int i = 0; i < (n); ++i) using namespace std; typedef vector<int> V; typedef long long ll; int n; int a[100000]; V t[100000]; int d[100000]; int p[17][100000]; int q[17][100000]; bool km[17][100000]; bool is_km(int p, int q, int r){ return ll(a[p] - a[q]) * (a[r] - a[q]) > 0 && a[p] != a[r]; } void dfs(int x){ for(int i: t[x]){ if(d[i] == -1){ d[i] = d[x] + 1; p[0][i] = x; dfs(i); } } } void init(){ fill_n(d + 1, n - 1, -1); p[0][0] = -1; dfs(0); rep(i, n){ q[0][i] = i; } fill_n(km[0] + 1, n - 1, true); for(int i = 1; i < 17; ++i){ rep(j, n){ int v = p[i - 1][j]; if(v != -1){ p[i][j] = p[i - 1][v]; q[i][j] = q[i - 1][v]; km[i][j] = km[i - 1][j] && km[i - 1][v] && is_km(p[0][v], v, q[i - 1][j]); } else{ p[i][j] = q[i][j] = -1; km[i][j] = false; } } } } #include <iostream> int up(int v, int x){ rep(i, 17){ if(x >> i & 1){ v = p[i][v]; } } return v; } int lca(int u, int v){ if(d[u] > d[v]){ swap(u, v); } v = up(v, d[v] - d[u]); if(u == v){ return u; } for(int i = 17 - 1; i >= 0; --i){ if(p[i][u] != p[i][v]){ u = p[i][u]; v = p[i][v]; } } return p[0][u]; } bool is_kml(int u, int v){ int x = d[v] - d[u]; rep(i, 17){ if(x >> i & 1){ int w = p[i][v]; if(!km[i][v] || (w != u && !km[1][q[i][v]])){ return false; } v = w; } } return true; } 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; t[x].push_back(y); t[y].push_back(x); } init(); int q; scanf("%d", &q); rep(i, q){ int u, v; scanf("%d%d", &u, &v); --u; --v; if(d[u] > d[v]){ swap(u, v); } int c = lca(u, v); /* cout << "lca: " << c + 1 << endl; cout << "v: " << v + 1 << endl; cout << "u: " << u + 1 << endl; cout << "c1: " << up(v, d[v] - d[c] - 1) + 1 << endl; cout << "c2: " << up(u, d[u] - d[c] - 1) + 1 << endl; cout << "about c:" << is_km(up(u, d[u] - d[c] - 1), c, up(v, d[v] - d[c] - 1)) << endl; cout << "cv: " << is_kml(c, v) << endl; cout << "cu: " << is_kml(c, u) << endl; */ if( u == c && d[v] - d[c] >= 2 && is_kml(c, v) && is_km(v, c, up(v, d[v] - d[c] - 1)) && is_km(c, v, p[0][v]) || u != c && is_kml(c, v) && is_kml(c, u) && is_km(up(u, d[u] - d[c] - 1), c, up(v, d[v] - d[c] - 1)) && is_km(u, v, p[0][v]) && is_km(v, u, p[0][u]) ){ puts("YES"); } else{ puts("NO"); } } return 0; }