oj.uz

Submission #222408

# Submission time Handle Problem Language Result Execution time Memory
222408 2020-04-13T06:49:54 Z jamielim Checker (COCI19_checker) C++14
35 / 110
 621 ms 87792 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 128 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 128 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 8 ms 1152 KB Output is correct
9 Correct 10 ms 1152 KB Output is correct
10 Incorrect 8 ms 1152 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 87544 KB Output is correct
2 Correct 621 ms 87792 KB Output is correct
3 Incorrect 548 ms 87672 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 611 ms 87672 KB Output is correct
2 Correct 617 ms 87544 KB Output is correct
3 Correct 403 ms 87672 KB Output is correct
4 Correct 417 ms 87544 KB Output is correct
5 Correct 394 ms 87680 KB Output is correct
6 Correct 484 ms 87416 KB Output is correct
7 Correct 483 ms 87420 KB Output is correct
8 Correct 393 ms 87416 KB Output is correct
9 Correct 396 ms 87480 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 128 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 8 ms 1152 KB Output is correct
9 Correct 10 ms 1152 KB Output is correct
10 Incorrect 8 ms 1152 KB Output isn't correct
11 Halted 0 ms 0 KB -