#include <bits/stdc++.h>
#include <atcoder/segtree>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _3oKjziw ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;
pii op(pii l,pii r){
return {min(l.fi,r.fi),max(l.se,r.se)};
}
pii e(){
return {1e9,-1};
}
void slv(){
int n;
cin>>n;
string s;
cin>>s;
vec(vec(pii)) adj(n);
rep(i,n-3){
int u,v,_c;
cin>>u>>v>>_c;
u--,v--;
adj[u].pb({v,_c});
adj[v].pb({u,_c});
}
atcoder::segtree<pii,op,e> seg(n);
rep(v,n){
for(auto edge : adj[v]){
int u=edge.fi;
seg.set(v,op(seg.get(v),{u,u}));
}
}
bool pok=1;
rep(v,n){
for(auto edge : adj[v]){
int u=edge.fi;
if(v>u) continue;
pii p=seg.prod(v+1,u);
if(p.fi<v or p.se>u){
pok=0;
}
}
}
if(not pok){
cout<<"neispravna triangulacija\n";
return;
}
rep(i,n-1){
adj[i].pb({i+1,s[i]-'0'});
adj[i+1].pb({i,s[i]-'0'});
}
adj[n-1].pb({0,s[n-1]-'0'});
adj[0].pb({n-1,s[n-1]-'0'});
std::map<pii,int> mp;
rep(v,n){
for(auto edge : adj[v]){
int u=edge.fi;
mp[{v,u}]=edge.se;
}
}
pok=1;
rep(v,n){
for(auto edge : adj[v]){
int u=edge.fi;
for(auto edge1 : adj[u]){
int u1=edge1.fi;
if(mp.find({v,u1})!=mp.end()){
if(mp[{v,u}]==mp[{u,u1}] or mp[{v,u}]==mp[{v,u1}] or mp[{u1,u}]==mp[{u1,v}]){
pok=0;
}
}
}
}
}
if(not pok){
cout<<"neispravno bojenje\n";
return;
}
cout<<"tocno\n";
}
int main(){
_3oKjziw;
int t;
cin>>t;
rep(cs,t)
slv();
//
return 0;
}
Compilation message
checker.cpp:2:10: fatal error: atcoder/segtree: No such file or directory
2 | #include <atcoder/segtree>
| ^~~~~~~~~~~~~~~~~
compilation terminated.
