Submission #1194523

#TimeUsernameProblemLanguageResultExecution timeMemory
1194523zNatsumiChecker (COCI19_checker)C++20
35 / 110
204 ms47076 KiB
#include <bits/stdc++.h> using namespace std; using ii = pair<int, int>; const int N = 2e5 + 5; int n, st[N<<2], depth[N], rt[N], up[N][20], timer, in[N], out[N]; bool vst[N]; vector<int> ad[N]; vector<ii> edge[3]; void update(int x, int y, int tl, int tr, int i){ if(tl == tr){ st[i] = max(st[i], y); return; } int tm = tl + tr >> 1; if(x <= tm) update(x, y, tl, tm, i<<1); else update(x, y, tm + 1, tr, i<<1|1); st[i] = max(st[i<<1], st[i<<1|1]); } int get(int l, int r, int tl, int tr, int i){ if(r < tl || tr < l || l > r) return 0; if(l <= tl && tr <= r) return st[i]; int tm = tl + tr >> 1; return max(get(l, r, tl, tm, i<<1), get(l, r, tm + 1, tr, i<<1|1)); } void dfs(int u, int p, int root){ in[u] = ++timer; vst[u] = true; rt[u] = root; for(int i = 1; i <= 17; i++) up[u][i] = up[up[u][i - 1]][i - 1]; for(auto v : ad[u]) if(v != p){ if(vst[v]){ cout << "neispravno bojenje"; exit(0); }else{ depth[v] = depth[u] + 1; up[v][0] = u; dfs(v, u, root); } } out[u] = ++timer; } bool anc(int u, int v){ return in[u] <= in[v] && out[v] <= out[u]; } int lca(int u, int v){ if(anc(u, v)) return u; if(anc(v, u)) return v; for(int i = 17; i >= 0; i--) if(up[u][i] && !anc(up[u][i], v)) u = up[u][i]; return up[u][0]; } int dist(int u, int v){ if(rt[u] != rt[v]) return -1; return depth[u] + depth[v] - depth[lca(u, v)]; } void solve(int x){ timer = 0; for(int i = 1; i <= n; i++){ ad[i].clear(); vst[i] = depth[i] = rt[i] = in[i] = out[i] = 0; for(int j = 0; j <= 17; j++) up[i][j] = 0; } for(auto [u, v] : edge[x]){ ad[u].push_back(v); ad[v].push_back(u); } for(int i = 1; i <= n; i++) if(!vst[i]) dfs(i, i, i); for(int i = 0; i <= 2; i++) if(i != x) for(auto [u, v] : edge[i]) if(dist(u, v) == 2){ cout << "neispravno bojenje"; exit(0); } } int32_t main(){ cin.tie(0)->sync_with_stdio(0); // #define task "test" // if(fopen(task ".inp", "r")){ // freopen(task ".inp", "r", stdin); // freopen(task ".out", "w", stdout); // } int _; cin >> _; cin >> n; for(int i = 1; i <= n; i++){ int v = i + 1 > n ? 1 : i + 1; char w; cin >> w; w -= '1'; ad[i].push_back(v); ad[v].push_back(i); edge[w].push_back({i, v}); } for(int i = 1; i <= n - 3; i++){ int u, v, c; cin >> u >> v >> c; ad[u].push_back(v); ad[v].push_back(u); edge[c - 1].push_back({u, v}); } for(int i = 1; i <= n; i++){ int x = 0; for(auto v : ad[i]) if(v > i) x = max(x, v); else if(get(v + 1, i - 1, 1, n, 1) > i) return cout << "neispravna triangulacija", 0; update(i, x, 1, n, 1); } for(int i = 0; i <= 2; i++) solve(i); cout << "tocno"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...