oj.uz

Submission #302305

# Submission time Handle Problem Language Result Execution time Memory
302305 2020-09-18T15:30:16 Z TMJN Simurgh (IOI17_simurgh) C++17
0 / 100
 1 ms 384 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

int N,M,D[500],ID[500][500];
bool B[500][500];

vector<int>find_roads(int n,vector<int>u,vector<int>v){
	N=n;
	M=u.size();
	assert(M==N*(N-1)/2);
	for(int i=0;i<M;i++){
		ID[u[i]][v[i]]=ID[v[i]][u[i]]=i;
	}
	for(int i=0;i<N;i++){
		vector<int>v;
		for(int j=0;j<N;j++){
			if(i==j)continue;
			v.push_back(ID[i][j]);
		}
		D[i]=count_common_roads(v);
	}
	int uni,K;
	uni=-1;
	K=-1;
	for(int i=0;i<N;i++){
		if(D[i]==1){
			uni=i;
			break;
		}
	}
	for(int i=uni+1;i<N;i++){
		if(D[i]==1){
			vector<int>v;
			for(int j=0;j<N;j++){
				if(j==uni||j==i)continue;
				v.push_back(ID[i][j]);
			}
			v.push_back(-1);
			for(int j=0;j<N;j++){
				if(j==uni)continue;
				if(j==i)continue;
				v.back()=ID[uni][j];
				if(count_common_roads(v)==2){
					K=j;
					break;
				}
			}
			break;
		}
	}
	B[uni][K]=B[K][uni]=true;
	for(int i=0;i<N;i++){
		if(i==uni)continue;
		int last_val=-1;
		for(int j=0;j<D[i];j++){
			int l,r;
			l=last_val;
			r=N-1;
			while(l+1!=r){
				int m=(l+r)/2;
				vector<int>v;
				int c=0;
				v.push_back(ID[uni][i]);
				for(int k=0;k<=last_val;k++){
					if(k==uni||k==i)continue;
					if(k==K)c=1;
					v.push_back(ID[uni][k]);
				}
				for(int k=m+1;k<N;k++){
					if(k==uni||k==i)continue;
					if(k==K)c=1;
					v.push_back(ID[uni][k]);
				}
				for(int k=last_val+1;k<=m;k++){
					if(k==uni||k==i)continue;
					v.push_back(ID[i][k]);
				}
				if(count_common_roads(v)>c){
					r=m;
				}
				else{
					l=m;
				}
			}
			B[i][r]=B[r][i]=true;
			last_val=r;
		}
	}
	vector<int>res;
	for(int i=0;i<N;i++){
		for(int j=i+1;j<N;j++){
			if(B[i][j])res.push_back(ID[i][j]);
		}
	}
	return res;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Incorrect 1 ms 384 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Incorrect 1 ms 384 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Incorrect 1 ms 384 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB correct
2 Incorrect 1 ms 384 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB correct
2 Incorrect 1 ms 384 KB WA in grader: NO
3 Halted 0 ms 0 KB -