Submission #222408

#	Time	Username	Problem	Language	Result	Execution time	Memory
222408		jamielim	Checker (COCI19_checker)	C++14	35 / 110	621 ms	87792 KiB

checker

#include <bits/stdc++.h>
using namespace std;

int main(){
	int t,n;
	scanf("%d%d",&t,&n);
	char c[n+5];
	scanf("%s",c);
	pair<pair<int,int>,int> p[n-3];
	for(int i=0;i<n-3;i++){
		scanf("%d%d%d",&p[i].first.first,&p[i].first.second,&p[i].second);
		if(p[i].first.first>p[i].first.second)swap(p[i].first.first,p[i].first.second);
		p[i].first.second*=-1;
		//printf("%d %d %d\n",p[i].first.first,p[i].first.second,p[i].second);
	}
	sort(p,p+n-3);
	for(int i=0;i<n-3;i++)p[i].first.second*=-1;
	for(int i=0;i<n-4;i++){
		if(p[i].first.first<p[i+1].first.first&&p[i+1].first.first<p[i].first.second&&p[i].first.second<p[i+1].first.second){
			printf("neispravna triangulacija"); //cross
			return 0;
		}else if(p[i].first==p[i+1].first){ //repeat diagonal
			printf("neispravna triangulacija");
			return 0;
		}
	}
	map<pair<int,int>,int> m;
	set<pair<int,int> > adj[n+5];
	for(int i=0;i<n;i++){
		int x=i+1,y=i+2; if(y==n+1)y=1;
		m[make_pair(x,y)]=c[i]-'0';m[make_pair(y,x)]=c[i]-'0';
		adj[x].insert(make_pair(y,c[i]-'0'));
		adj[y].insert(make_pair(x,c[i]-'0'));
	}
	for(int i=0;i<n-3;i++)m[p[i].first]=p[i].second;
	for(int i=0;i<n-3;i++){
		m[p[i].first]=p[i].second;
		adj[p[i].first.first].insert(make_pair(p[i].first.second,p[i].second));
		adj[p[i].first.second].insert(make_pair(p[i].first.first,p[i].second));
	}
	queue<int> q;
	for(int i=1;i<=n;i++){
		if((int)adj[i].size()==2)q.push(i);
	}
	while(!q.empty()){
		int cur=q.front();q.pop();
		//printf("%d\n",cur);
		if((int)adj[cur].size()!=2)continue;
		pair<int,int> x=(*adj[cur].begin()),y=(*(++adj[cur].begin()));
		int z=m[make_pair(x.first,y.first)];
		if(z!=x.second&&z!=y.second&&x.second!=y.second){
			adj[x.first].erase(make_pair(cur,x.second));
			adj[y.first].erase(make_pair(cur,y.second));
			if((int)adj[x.first].size()==2)q.push(x.first);
			if((int)adj[y.first].size()==2)q.push(y.first);
		}else{
			printf("neispravno bojenje");
			return 0;
		}
	}
	printf("tocno");
}

Compilation message (stderr)

checker.cpp: In function 'int main()':
checker.cpp:6:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&t,&n);
  ~~~~~^~~~~~~~~~~~~~
checker.cpp:8:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",c);
  ~~~~~^~~~~~~~
checker.cpp:11:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&p[i].first.first,&p[i].first.second,&p[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 23
• Subtask 4: 23 / 23
• Subtask 5: 0 / 35