oj.uz

답안 #222454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
222454 2020-04-13T07:40:23 Z errorgorn Checker (COCI19_checker) C++14
0 / 110
 746 ms 97772 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);
		
		//cout<<"DEBUG: "<<i<<" "<<*it<<" "<<j<<endl;
		tri.push_back(trip(i,j,*it));
		
		if (i<j && i<*it && *it<j) return true;
		if (j<i && (i<*it || *it<j)) return true;
	
		
		al[i].erase(j);
		al[j].erase(i);
		
		if (dfs(i,*it)||dfs(*it,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:126:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (tri.size()!=n-2) return 1;
      ~~~~~~~~~~^~~~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 27 ms 19584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 27 ms 19584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 745 ms 97628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 746 ms 97772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 27 ms 19584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -