| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1013121 |
2024-07-03T08:11:08 Z |
vjudge1 |
Checker (COCI19_checker) |
C++17 |
|
3000 ms |
45016 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int const N=2e5+5;
int const mod=1e9+7;
int bk[N],fr[N];
int n;
map<pair<int,int>,int> mp;
bool check1(){
for(int i=1;i<n;i++)
if(fr[i+1]+1>bk[i])
return 0;
if(fr[1]+1>bk[n])
return 0;
return 1;
}
bool is(int a,int b){
if(mp.find({a,b})!=mp.end())
return 1;
return 0;
}
bool diff(int a,int b,int c){
if(mp[{a,b}]!=mp[{b,c}] && mp[{b,c}]!=mp[{c,a}])
return 1;
return 0;
}
bool check2(){
vector<int> v1,v2;
for (int i = 1; i <=n; ++i)
v1.push_back(i);
while(v1.size()>2){
int sz=v1.size();
if(is(v1[sz-1],v1[1])){
if(diff(v1[sz-1],v1[0],v1[1])==0)
return 0;
}
else
v2.push_back(v1[0]);
for(int i=1;i<sz-1;i++){
if(is(v1[i-1],v1[i+1])){
if(diff(v1[i-1],v1[i],v1[i+1])==0)
return 0;
}
else
v2.push_back(v1[i]);
}
if(is(v1[sz-2],v1[0])){
if(diff(v1[sz-2],v1[sz-1],v1[0])==0)
return 0;
}
else
v2.push_back(v1[sz-1]);
v1=v2;
// for(int i:v1)
// cout<<i<<' ';
// cout<<endl;
v2.clear();
}
return 1;
}
int main(){
int t;
cin>>t;
cin>>n;
string col;
cin>>col;
for(int i=0;i<n-1;i++)
mp[{i+1,i+2}]=col[i]-'0';
mp[{n,1}]=col[n-1]-'0';
for(int i=1;i<=n;i++){
fr[i]=2;
bk[i]=n;
}
for (int i = 0; i < n-3; ++i)
{
int a,b,c;
cin>>a>>b>>c;
mp[{a,b}]=c;
mp[{b,a}]=c;
if(a>b)
swap(a,b);
int ba=(b-a)+1;
fr[a]=max(fr[a],ba);
bk[a]=min(bk[a],ba);
int ab=(n+1)-(b-a);
fr[b]=max(fr[b],ab);
bk[b]=min(bk[b],ab);
}
// for (int i = 1; i <=n; ++i)
// cout<<fr[i]<<' '<<bk[i]<<endl;
if(check1()==0)
cout<<"neispravna triangulacija"<<endl;
else if(check2()==0)
cout<<"neispravno bojenje"<<endl;
else
cout<<"tocno"<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
464 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
464 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1390 ms |
42076 KB |
Output is correct |
| 2 |
Correct |
1362 ms |
42080 KB |
Output is correct |
| 3 |
Correct |
311 ms |
39752 KB |
Output is correct |
| 4 |
Correct |
305 ms |
39968 KB |
Output is correct |
| 5 |
Correct |
288 ms |
39648 KB |
Output is correct |
| 6 |
Execution timed out |
3061 ms |
42080 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1451 ms |
42076 KB |
Output is correct |
| 2 |
Correct |
1421 ms |
42080 KB |
Output is correct |
| 3 |
Correct |
558 ms |
41952 KB |
Output is correct |
| 4 |
Correct |
532 ms |
45016 KB |
Output is correct |
| 5 |
Correct |
351 ms |
43944 KB |
Output is correct |
| 6 |
Execution timed out |
3073 ms |
44992 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
464 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
