oj.uz

Submission #95917

# Submission time Handle Problem Language Result Execution time Memory
95917 2019-02-04T05:09:17 Z jangwonyoung Simurgh (IOI17_simurgh) C++14
19 / 100
 124 ms 5140 KB 
#include "simurgh.h"
#include<iostream>
#include<queue>
using namespace std;
vector<int>r;
vector<int>s;
int c;
int qry(){
	for(int i=0; i<r.size() ;i++) r[i]--;
	//cout << "QRY: ";
	//for(int i=0; i<r.size() ;i++) cout << r[i] << ' ';
	//cout << endl;
	int ans=count_common_roads(r);
	r.clear();r.shrink_to_fit();
	//cout << "RES: " << ans << endl;
	return ans;
}
int e[501][501];
int g[501][501];
int val[501];
bool sh[501];
int N;
int make(int id){
	//cout << "Make " << id << endl;
	for(int i=1; i<=id ;i++) sh[i]=false;
	for(auto cur:s) sh[cur]=true;
	int ext=0;
	for(int i=2; i<id ;i++){
		if(!sh[i]){
			r.push_back(e[1][i]);
			ext+=g[1][i];
		}
		else r.push_back(e[i][id]);
	}
	if(!sh[1]){
		int cur=s[0];
		r.push_back(e[1][cur]);
		ext+=g[1][cur];
	}
	else r.push_back(e[1][id]);
	for(int i=id+1; i<=N ;i++) r.push_back(e[1][i]);
	int res=qry();
	s.clear();s.shrink_to_fit();
	return res-ext;
}
void tzuyu(int id,int l,int r){
	for(int j=l; j<=r ;j++) s.push_back(j);
	int cv=make(id)-c;
	if(cv==0) return;
	if(l==r){
		g[l][id]=1;
		return;
	}
	int mid=(l+r)/2;
	tzuyu(id,l,mid);
	tzuyu(id,mid+1,r);
}
vector<int>find_roads(int n,vector<int> u,vector<int> v){
	N=n;
	int m=u.size();
	if(m!=n*(n-1)/2){
		vector<int>rr(n-1);
		for(int i=0; i<n-1 ;i++) rr[i]=i;
		return rr;
	}
	if(n==2){r.push_back(0);return r;}
	for(int i=0; i<m ;i++) e[u[i]+1][v[i]+1]=e[v[i]+1][u[i]+1]=i+1;
	int sum=0;
	for(int i=1; i<=n ;i++){
		for(int j=1; j<=n ;j++) if(i!=j) r.push_back(e[j][j%n+1]);
		val[i]=qry();
		sum+=val[i];
	}
	g[1][2]=sum/(n-1)-val[1];
	for(int i=3; i<=n ;i++){
		for(int j=1; j<i ;j++) s.push_back(j);
		int x=make(i);
		for(int j=2; j<i ;j++) s.push_back(j);
		int y=make(i);
		s.push_back(1);
		int z=make(i);
		c=y+z-x;
		g[1][i]=z-c;
		tzuyu(i,2,i-1);
	}
	for(int i=1; i<=n ;i++)
		for(int j=i+1; j<=n ;j++)
			if(g[i][j]) r.push_back(e[i][j]-1);
	return r;
}

Compilation message

simurgh.cpp: In function 'int qry()':
simurgh.cpp:9:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<r.size() ;i++) r[i]--;
               ~^~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 21.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB correct
2 Correct 2 ms 376 KB correct
3 Correct 79 ms 3588 KB correct
4 Correct 124 ms 5016 KB correct
5 Correct 122 ms 5140 KB correct
6 Correct 79 ms 5076 KB correct
7 Correct 110 ms 4624 KB correct
8 Correct 109 ms 4668 KB correct
9 Correct 122 ms 5016 KB correct
10 Correct 122 ms 4984 KB correct
11 Correct 113 ms 5084 KB correct
12 Correct 124 ms 4984 KB correct
13 Correct 2 ms 376 KB correct
14 Correct 104 ms 5008 KB correct
15 Correct 121 ms 4956 KB correct

Subtask #5
0 / 30.0

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