#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back
using namespace std;
const int N=1e6,M=3e3+2,mod=1e9+7;
int seg[N],x[N],y[N],z[N];
vector< pair<int,int> > v[N];
vector<int>adj[N];
map< pair<int,int> , int > col;
void update(int v,int tl,int tr,int index){
if(tl==tr){
/*if(seg[v]==0)
seg2[v]=1;
else
seg3[v]=1;*/
seg[v]=!seg[v];
return ;
}
int tm=(tl+tr)/2;
if(index<=tm)
update(v*2,tl,tm,index);
else
update(v*2+1,tm+1,tr,index);
seg[v]=seg[v*2]+seg[v*2+1];
/*seg2[v]=seg2[v*2]+seg2[v*2+1];
seg3[v]=seg3[v*2]+seg3[v*2+1];*/
}
int get(int v,int tl,int tr,int l,int r){
if(tl>r||tr<l)
return 0;
if(tl>=l&&tr<=r)
return seg[v];
int tm=(tl+tr)/2;
return get(v*2,tl,tm,l,r)+get(v*2+1,tm+1,tr,l,r);
}
main(){
int xx;
cin>>xx;
int n;
cin>>n;
string s;
cin>>s;
for(int i=1;i<=n;i++){
if(i==n){
col[{n,1}]=s[i-1]-'0';
col[{1,n}]=s[i-1]-'0';
adj[1].pb(n);
adj[n].pb(1);
}
col[{i,i+1}]=s[i-1]-'0';
col[{i+1,i}]=s[i-1]-'0';
adj[i].pb(i+1);
adj[i+1].pb(i);
}
map<int,int>mp;
for(int i=0;i<n-3;i++){
cin>>x[i]>>y[i]>>z[i];
col[{x[i],y[i]}]=z[i];
col[{y[i],x[i]}]=z[i];
adj[x[i]].pb(y[i]);
adj[y[i]].pb(x[i]);
v[min(x[i],y[i])].pb({1,i+1});
v[max(x[i],y[i])].pb({0,i+1});
}
bool Final_ans=0;
for(int i=1;i<=n;i++){
for(auto x:v[i])
if(x.F==0)
update(1,1,n,mp[x.S]);
for(auto x:v[i]){
if(x.F==1)
continue;
int xxx=get(1,1,n,mp[x.S]+1,i);
if(xxx!=0)
Final_ans=1;
}
for(auto x:v[i]){
if(x.F==1)
mp[x.S]=i,update(1,1,n,i);
}
}
int Final_ans2=0;
for(int i=0;i<n-3;i++){
if(adj[x[i]].size()<adj[y[i]].size()){
for(int j=0;j<adj[x[i]].size();j++){
if(col[{y[i],adj[x[i]][j]}]==0)
continue;
if(col[{y[i],adj[x[i]][j]}]==col[{x[i],adj[x[i]][j]}]||col[{y[i],adj[x[i]][j]}]==col[{y[i],x[i]}]||col[{x[i],adj[x[i]][j]}]==col[{x[i],y[i]}])
Final_ans2=1;
}
}
else{
for(int j=0;j<adj[y[i]].size();j++){
if(col[{x[i],adj[y[i]][j]}]==0)
continue;
if(col[{x[i],adj[y[i]][j]}]==col[{y[i],adj[y[i]][j]}]||col[{x[i],adj[y[i]][j]}]==col[{y[i],x[i]}]||col[{y[i],adj[y[i]][j]}]==col[{x[i],y[i]}])
Final_ans2=1;
}
}
}
if(Final_ans==1)
cout<<"neispravna triangulacija"<<endl;
else if(Final_ans==0&&Final_ans2==0)
cout<<"tocno"<<endl;
else if(Final_ans==0&&Final_ans2==1)
cout<<"neispravno bojenje"<<endl;
return 0;
}
Compilation message
checker.cpp:57:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
57 | main(){
| ^~~~
checker.cpp: In function 'int main()':
checker.cpp:136:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int j=0;j<adj[x[i]].size();j++){
| ~^~~~~~~~~~~~~~~~~
checker.cpp:150:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for(int j=0;j<adj[y[i]].size();j++){
| ~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
47316 KB |
Output is correct |
2 |
Correct |
24 ms |
47272 KB |
Output is correct |
3 |
Incorrect |
24 ms |
47308 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
47316 KB |
Output is correct |
2 |
Correct |
24 ms |
47272 KB |
Output is correct |
3 |
Incorrect |
24 ms |
47308 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2039 ms |
163340 KB |
Output is correct |
2 |
Correct |
2035 ms |
163052 KB |
Output is correct |
3 |
Correct |
2033 ms |
163300 KB |
Output is correct |
4 |
Correct |
1996 ms |
163480 KB |
Output is correct |
5 |
Correct |
1991 ms |
163852 KB |
Output is correct |
6 |
Correct |
1973 ms |
146228 KB |
Output is correct |
7 |
Correct |
1875 ms |
142472 KB |
Output is correct |
8 |
Correct |
1929 ms |
144512 KB |
Output is correct |
9 |
Correct |
1881 ms |
143368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1989 ms |
163468 KB |
Output is correct |
2 |
Correct |
1996 ms |
163488 KB |
Output is correct |
3 |
Correct |
1981 ms |
163592 KB |
Output is correct |
4 |
Correct |
2039 ms |
165892 KB |
Output is correct |
5 |
Correct |
2031 ms |
165948 KB |
Output is correct |
6 |
Correct |
1932 ms |
147176 KB |
Output is correct |
7 |
Correct |
1899 ms |
145844 KB |
Output is correct |
8 |
Correct |
1978 ms |
148180 KB |
Output is correct |
9 |
Correct |
1871 ms |
145172 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
47316 KB |
Output is correct |
2 |
Correct |
24 ms |
47272 KB |
Output is correct |
3 |
Incorrect |
24 ms |
47308 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |