| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 940322 | 1075508020060209tc | Checker (COCI19_checker) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int ttt;
int n;
vector<pair<int,int>>e[200005];
vector<pair<int,int>>ne[200005];
vector<int>inter[400005];
bool cmp(int i,int j){
if(e[i].size()<e[j].size()){return 1;}
if(e[i].size()>e[j].size()){return 0;}
return i<j;
}
bool cmp2(pair<int,int>i,pair<int,int>j){
return cmp(i.first,j.first);
}
int clr[400005];
bool cyc3(){
for(int i=1;i<=n;i++){
for(int j=0;j<e[i].size();j++){
int v=e[i][j].first;
if(cmp(i,v)){
ne[i].push_back({v,e[i].second});
}
}
sort(ne[i].begin(),ne[i].end());
}
int ret=0;
for(int a=1;a<=n;a++){
for(pair<int,int>pr:ne[a]){
int b=pr.first;
clr[b]=pr.second;
for(pair<int,int>pr2:ne[b]){
int c=pr.first;
if(mp[{a,c}]&&pr.second+clr[c]+mp[{a,c}]%3==0){
ret++;
}
}
}
}
return ret==n-2;
}
void solve(){
cin>>n;
string s;
cin>>s;
for(int i=0;i<s.size();i++){
int v=s[i]-'0';
int a=i+1;int b=i+2;
if(i==n-1){
b=1;
}
e[a].push_back({b,v});
e[b].push_back({a,v});
}
vector<pair<int,int>>seg;
for(int i=1;i<=n-3;i++){
int a;int b;int c;
cin>>a>>b>>c;
if(a>b){swap(a,b);}
e[a].push_back({b,c});
e[b].push_back({a,c});
seg.push_back({a,b});
seg.push_back({b,a+n});
}
sort(seg.begin(),seg.end());
int rt=seg[0].second;
for(int i=1;i<seg.size();i++){
if(seg[i].first<rt){
cout<<"neispravna triangulacija\n";
return;
}
rt=max(rt,seg[i].second);
}
cout<<"tocno\n";
}
signed main(){
cin>>ttt;
while(ttt--)solve();
}