oj.uz

Submission #222519

# Submission time Handle Problem Language Result Execution time Memory
222519 2020-04-13T08:36:50 Z errorgorn Checker (COCI19_checker) C++14
110 / 110
 1149 ms 116600 KB 
#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;
 
bool dfs(int i,int j){ 
	//cout<<i<<" "<<j<<endl;
	//note here that it returns true if triangulation does not exist
	
	if ((j+1)%n==i){
		al[i].erase(j);
		al[j].erase(i);
		return false;
	}
	else{
		auto curr=al[i].find(j);
		auto it=(curr==(--al[i].end()))?al[i].begin():next(curr);
		
		int temp=*it;
		
		//cout<<"DEBUG: "<<i<<" "<<*it<<" "<<j<<endl;
		tri.push_back(trip(i,j,*it));
		
		if (i<j && i<temp && temp<j) return true;
		if (j<i && (i<temp || temp<j)) return true;
		if (!al[j].count(temp)) return true;
		
		al[i].erase(j);
		al[j].erase(i);
		
		if (dfs(i,temp)||dfs(temp,j)) return true;
		
		return false;
	}
	
}
 
int main(){
	//freopen("input.txt","r",stdin);
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n; //bye bye
	cin>>n;
	
	cin>>sides;
	
	for (int x=0;x<n;x++){
		al[x].insert((x+1)%n);
		al[(x+1)%n].insert(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--;
		
		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";
			return 0;
		}
	}
	else {
		if (dfs(0,1)){
			cout<<"neispravna triangulacija";
			return 0;
		}
	}
	
	//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";
				return 0;
			}
	}
	
	cout<<"tocno";
	
}
 
//neispravna triangulacija -2
//neispravno bojenje -1
//tocno 0

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 12 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 11 ms 9728 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 12 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 11 ms 9728 KB Output is correct
8 Correct 15 ms 10624 KB Output is correct
9 Correct 15 ms 10624 KB Output is correct
10 Correct 14 ms 10624 KB Output is correct
11 Correct 13 ms 10624 KB Output is correct
12 Correct 14 ms 10752 KB Output is correct
13 Correct 14 ms 10624 KB Output is correct
14 Correct 14 ms 10624 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 965 ms 101064 KB Output is correct
2 Correct 964 ms 101108 KB Output is correct
3 Correct 781 ms 100984 KB Output is correct
4 Correct 757 ms 98052 KB Output is correct
5 Correct 770 ms 97824 KB Output is correct
6 Correct 1138 ms 110584 KB Output is correct
7 Correct 1078 ms 111616 KB Output is correct
8 Correct 874 ms 99396 KB Output is correct
9 Correct 877 ms 99996 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 975 ms 100948 KB Output is correct
2 Correct 969 ms 101108 KB Output is correct
3 Correct 850 ms 101112 KB Output is correct
4 Correct 793 ms 101256 KB Output is correct
5 Correct 816 ms 101112 KB Output is correct
6 Correct 1089 ms 116600 KB Output is correct
7 Correct 1092 ms 114984 KB Output is correct
8 Correct 960 ms 112068 KB Output is correct
9 Correct 915 ms 111396 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 12 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 10 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 11 ms 9728 KB Output is correct
8 Correct 15 ms 10624 KB Output is correct
9 Correct 15 ms 10624 KB Output is correct
10 Correct 14 ms 10624 KB Output is correct
11 Correct 13 ms 10624 KB Output is correct
12 Correct 14 ms 10752 KB Output is correct
13 Correct 14 ms 10624 KB Output is correct
14 Correct 14 ms 10624 KB Output is correct
15 Correct 965 ms 101064 KB Output is correct
16 Correct 964 ms 101108 KB Output is correct
17 Correct 781 ms 100984 KB Output is correct
18 Correct 757 ms 98052 KB Output is correct
19 Correct 770 ms 97824 KB Output is correct
20 Correct 1138 ms 110584 KB Output is correct
21 Correct 1078 ms 111616 KB Output is correct
22 Correct 874 ms 99396 KB Output is correct
23 Correct 877 ms 99996 KB Output is correct
24 Correct 975 ms 100948 KB Output is correct
25 Correct 969 ms 101108 KB Output is correct
26 Correct 850 ms 101112 KB Output is correct
27 Correct 793 ms 101256 KB Output is correct
28 Correct 816 ms 101112 KB Output is correct
29 Correct 1089 ms 116600 KB Output is correct
30 Correct 1092 ms 114984 KB Output is correct
31 Correct 960 ms 112068 KB Output is correct
32 Correct 915 ms 111396 KB Output is correct
33 Correct 977 ms 101240 KB Output is correct
34 Correct 1000 ms 101240 KB Output is correct
35 Correct 771 ms 99580 KB Output is correct
36 Correct 715 ms 97796 KB Output is correct
37 Correct 941 ms 101368 KB Output is correct
38 Correct 884 ms 101220 KB Output is correct
39 Correct 832 ms 101152 KB Output is correct
40 Correct 1149 ms 111344 KB Output is correct
41 Correct 1142 ms 116536 KB Output is correct
42 Correct 950 ms 116104 KB Output is correct
43 Correct 1086 ms 112604 KB Output is correct