oj.uz

Submission #222509

# Submission time Handle Problem Language Result Execution time Memory
222509 2020-04-13T08:33:01 Z errorgorn Checker (COCI19_checker) C++14
35 / 110
 1092 ms 118904 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;
     
    ii start=ii(-1,-1);
     
    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,temp));
    		
    		if (i<j && i<temp && temp<j) return true;
    		if (j<i && (i<temp || temp<j)) return true;
    	
    		
    		al[i].erase(j);
    		al[j].erase(i);
    		
    		if (dfs(i,temp)||dfs(temp,j)) return true;
    		
    		return false;
    	}
    	
    }
     
    int main(){
    	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--;
    		if ((a+2)%n==b) start=ii(a,b);
    		else if ((b+2)%n==a) start=ii(b,a);
    		
    		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 (start==ii(-1,-1)){
    			cout<<"neispravna triangulacija";
    			return 0;
    		} 
    		
    		al[start.first].erase((start.first+1)%n);
    		al[(start.first+1)%n].erase(start.first);
    		
    		al[start.second].erase((start.first+1)%n);
    		al[(start.first+1)%n].erase(start.second);
    		
    		if (dfs(start.first,start.second)){
    			cout<<"neispravna triangulacija";
    			return 0;
    		}
     
    		tri.push_back(trip(start.first,(start.first+1)%n,(start.first+2)%n));
    	}
    	
    	//now we check for legit colours
    	
    	if (tri.size()!=n-2) return 1;
    	
    	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

Compilation message

checker.cpp: In function 'int main()':
checker.cpp:127:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (tri.size()!=n-2) return 1;
          ~~~~~~~~~~^~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 11 ms 9728 KB Output is correct
6 Correct 10 ms 9856 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 14 ms 10624 KB Output is correct
9 Correct 15 ms 10624 KB Output is correct
10 Incorrect 13 ms 10624 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 973 ms 101288 KB Output is correct
2 Correct 968 ms 101084 KB Output is correct
3 Incorrect 952 ms 101240 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 967 ms 101240 KB Output is correct
2 Correct 980 ms 101240 KB Output is correct
3 Correct 887 ms 101240 KB Output is correct
4 Correct 865 ms 101036 KB Output is correct
5 Correct 794 ms 101164 KB Output is correct
6 Correct 1092 ms 118900 KB Output is correct
7 Correct 1090 ms 118900 KB Output is correct
8 Correct 1040 ms 118900 KB Output is correct
9 Correct 911 ms 118904 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 11 ms 9728 KB Output is correct
6 Correct 10 ms 9856 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 14 ms 10624 KB Output is correct
9 Correct 15 ms 10624 KB Output is correct
10 Incorrect 13 ms 10624 KB Output isn't correct
11 Halted 0 ms 0 KB -