#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |