oj.uz

Submission #222524

# Submission time Handle Problem Language Result Execution time Memory
222524 2020-04-13T08:42:08 Z errorgorn Checker (COCI19_checker) C++14
110 / 110
 1169 ms 114172 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'

struct custom_hash {
    typedef unsigned long long ull;
    const ull FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    static ull splitmix64(ull x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(ll x) const {
        return splitmix64(x + FIXED_RANDOM);
    }
    size_t operator()(const pair<int,int> &i)const{
        return splitmix64((((ll)i.first)^(((ll)i.second)<<32))+FIXED_RANDOM);
    }
};


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;
unordered_map<ii,char,custom_hash> 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;
	}
	
	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 11 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 10 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 11 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 10 ms 9728 KB Output is correct
8 Correct 14 ms 10624 KB Output is correct
9 Correct 13 ms 10624 KB Output is correct
10 Correct 13 ms 10624 KB Output is correct
11 Correct 13 ms 10624 KB Output is correct
12 Correct 13 ms 10624 KB Output is correct
13 Correct 17 ms 10752 KB Output is correct
14 Correct 13 ms 10624 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1096 ms 97780 KB Output is correct
2 Correct 1079 ms 97788 KB Output is correct
3 Correct 909 ms 97660 KB Output is correct
4 Correct 838 ms 92412 KB Output is correct
5 Correct 820 ms 92152 KB Output is correct
6 Correct 1169 ms 107132 KB Output is correct
7 Correct 1134 ms 108924 KB Output is correct
8 Correct 927 ms 93824 KB Output is correct
9 Correct 912 ms 94560 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1081 ms 97776 KB Output is correct
2 Correct 1086 ms 97916 KB Output is correct
3 Correct 962 ms 97920 KB Output is correct
4 Correct 909 ms 97912 KB Output is correct
5 Correct 939 ms 97980 KB Output is correct
6 Correct 1133 ms 114172 KB Output is correct
7 Correct 1165 ms 112508 KB Output is correct
8 Correct 969 ms 108796 KB Output is correct
9 Correct 961 ms 108660 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 11 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 10 ms 9728 KB Output is correct
8 Correct 14 ms 10624 KB Output is correct
9 Correct 13 ms 10624 KB Output is correct
10 Correct 13 ms 10624 KB Output is correct
11 Correct 13 ms 10624 KB Output is correct
12 Correct 13 ms 10624 KB Output is correct
13 Correct 17 ms 10752 KB Output is correct
14 Correct 13 ms 10624 KB Output is correct
15 Correct 1096 ms 97780 KB Output is correct
16 Correct 1079 ms 97788 KB Output is correct
17 Correct 909 ms 97660 KB Output is correct
18 Correct 838 ms 92412 KB Output is correct
19 Correct 820 ms 92152 KB Output is correct
20 Correct 1169 ms 107132 KB Output is correct
21 Correct 1134 ms 108924 KB Output is correct
22 Correct 927 ms 93824 KB Output is correct
23 Correct 912 ms 94560 KB Output is correct
24 Correct 1081 ms 97776 KB Output is correct
25 Correct 1086 ms 97916 KB Output is correct
26 Correct 962 ms 97920 KB Output is correct
27 Correct 909 ms 97912 KB Output is correct
28 Correct 939 ms 97980 KB Output is correct
29 Correct 1133 ms 114172 KB Output is correct
30 Correct 1165 ms 112508 KB Output is correct
31 Correct 969 ms 108796 KB Output is correct
32 Correct 961 ms 108660 KB Output is correct
33 Correct 1072 ms 97912 KB Output is correct
34 Correct 1075 ms 97788 KB Output is correct
35 Correct 858 ms 94972 KB Output is correct
36 Correct 824 ms 92280 KB Output is correct
37 Correct 1048 ms 97916 KB Output is correct
38 Correct 981 ms 97856 KB Output is correct
39 Correct 915 ms 97916 KB Output is correct
40 Correct 1151 ms 108156 KB Output is correct
41 Correct 1134 ms 113788 KB Output is correct
42 Correct 957 ms 113528 KB Output is correct
43 Correct 1065 ms 109176 KB Output is correct