#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
//#define endl '\n'
int n;
string sides;
set<int> al[200005];
struct trip{
int a,b,c;
trip (int _a,int _b,int _c){
a=_a,b=_b,c=_c;
}
};
vector<trip> tri;
map<ii,char> color;
ii start=ii(-1,-1);
bool dfs(int i,int j){
//cout<<i<<" "<<j<<endl;
//note here that it returns true if triangulation does not exist
if ((j+2)%n==i){
tri.push_back(trip( i, j, (j+1)%n ));
return false;
}
else{
if (al[i].size()==1){
if (al[j].count((i-1+n)%n)){
al[i].erase(j);
al[j].erase(i);
if (dfs((i-1+n)%n,j)) return true;
return false;
}
else return true;
}
auto curr=al[i].find(j);
auto it=(curr==(--al[i].end()))?al[i].begin():next(curr);
//cout<<"DEBUG: "<<i<<" "<<*it<<" "<<j<<endl;
if (i<j && i<*it && *it<j) return true;
if (j<i && (*it<i || *it<j)) return true;
al[i].erase(j);
al[j].erase(i);
if (!al[j].count(*it)){
if ((j+1)%n==*it){
if (dfs(i,*it)) return true;
}
else return true;
}
else if (dfs(i,*it)||dfs(*it,j)) return true;
tri.push_back(trip(i,j,*it));
return false;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n; //bye bye
cin>>n;
cin>>sides;
for (int x=0;x<n;x++){
color[ii(x,(x+1)%n)]=sides[x];
color[ii((x+1)%n,x)]=sides[x];
}
int a,b;
char c;
for (int x=3;x<n;x++){
cin>>a>>b>>c;
a--,b--;
if ((a+2)%n==b) start=ii(a,b);
else if ((b+2)%n==a) start=ii(b,a);
al[a].insert(b);
al[b].insert(a);
color[ii(a,b)]=c;
color[ii(b,a)]=c;
}
//we need another case for n==4 bruh
if (n==4){
if (a>b) swap(a,b);
if (a==0 && b==2){
tri.push_back(trip(0,1,2));
tri.push_back(trip(2,3,0));
}
else if (a==1 && b==3){
tri.push_back(trip(1,2,3));
tri.push_back(trip(3,0,1));
}
else{
cout<<"neispravna triangulacija"<<endl;
return 0;
}
}
else if (start==ii(-1,-1) || dfs(start.first,start.second)){
cout<<"neispravna triangulacija"<<endl;
return 0;
}
else{
tri.push_back(trip(start.first,(start.first+1)%n,(start.first+2)%n));
}
//now we check for legit colours
for (auto &it:tri){
//cout<<it.a<<" "<<it.b<<" "<<it.c<<endl;
//cout<<color[ii(it.a,it.b)]<<" "<<color[ii(it.b,it.c)]<<" "<<color[ii(it.c,it.a)]<<endl;
if (color[ii(it.a,it.b)]==color[ii(it.a,it.c)] ||
color[ii(it.b,it.a)]==color[ii(it.b,it.c)] ||
color[ii(it.c,it.a)]==color[ii(it.c,it.b)] ){
cout<<"neispravno bojenje"<<endl;
return 0;
}
}
cout<<"tocno"<<endl;
}
//neispravna triangulacija -2
//neispravno bojenje -1
//tocno 0
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
760 ms |
78980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
818 ms |
78996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
