oj.uz

Submission #24668

# Submission time Handle Problem Language Result Execution time Memory
24668 2017-06-10T20:39:26 Z jiangzhi ICC (CEOI16_icc) C++11
61 / 100
 186 ms 2092 KB 
#include <cstdio>
#include <vector>
#include <algorithm> 
#include "icc.h"

using namespace std;

const int N = 110;

int a[N];
int size_a;
int b[N];
int size_b;

int t1[N];
int size_t1;
int t2[N];
int size_t2;

int pai[N];

vector<int> aux[N];

int find(int a){
	if(pai[a]==a)return a;
	return pai[a] = find(pai[a]);
}

void run(int n){
	vector<int> total;
	for(int i = 1; i <= n; i++){
		total.push_back(i);
		aux[i].push_back(i);
		pai[i]=i;
	}		
	for(int cas = 1; cas <= n - 1; cas++){
		while(1){
			random_shuffle(total.begin(),total.end());
			//printf("\n");
			size_a = 0;
			size_b = 0;
			for(int i = 0; i < total.size(); i++){
				if(i%2==0){
					for(int j = 0; j < aux[total[i]].size(); j++){
						a[size_a++]=aux[total[i]][j];
					}
				}
				else{
					for(int j = 0; j < aux[total[i]].size(); j++){
						b[size_b++]=aux[total[i]][j];
					}
				}
			}
			if(query(size_a,size_b,a,b))break;
		}
		while(size_a!=1){
			size_t1 = 0;
			size_t2 = 0;
			for(int i = 0; i < size_a; i++){

				if(i%2==0){
					t1[size_t1++]=a[i];
				}
				else{
					t2[size_t2++]=a[i];
				}
			}
			if(query(size_t1,size_b,t1,b)){
				size_a = size_t1;
				for(int i = 0; i < size_t1; i++){
					a[i]=t1[i];
				}
			}
			else{
				size_a = size_t2;
				for(int i = 0; i < size_t2; i++){
					a[i]=t2[i];
				}
			}
		}
		while(size_b!=1){
			size_t1 = 0;
			size_t2 = 0;
			for(int i = 0; i < size_b; i++){
				if(i%2==0){
					t1[size_t1++]=b[i];
				}
				else{
					t2[size_t2++]=b[i];
				}
			}
			if(query(size_a,size_t1,a,t1)){
				size_b=size_t1;
				for(int i = 0; i < size_t1; i++){
					b[i]=t1[i];
				}
			}
			else{
				size_b=size_t2;
				for(int i = 0; i < size_t2; i++){
					b[i]=t2[i];
				}
			}
		}
		setRoad(a[0],b[0]);
		if(cas==n-1)return;

		a[0]=find(a[0]);
		b[0]=find(b[0]);
		//if(a[0]==b[0])continue;
		int val;
		if(aux[a[0]].size()>aux[b[0]].size()){
			for(int i = 0; i < aux[b[0]].size(); i++){
				aux[a[0]].push_back(aux[b[0]][i]);
			}
			aux[b[0]].clear();
			val = b[0];
			pai[b[0]]=a[0];
		}
		else{
			for(int i = 0; i < aux[a[0]].size(); i++){
				aux[b[0]].push_back(aux[a[0]][i]);
			}			
			aux[a[0]].clear();
			val = a[0];
			pai[a[0]]=b[0];
		}
		vector<int>total2;
		for(int i = 0; i < total.size(); i++){
			if(total[i]!=val)total2.push_back(total[i]);
		}
		total.clear();
		for(int i = 0; i < total2.size(); i++){
			total.push_back(total2[i]);
		}
	}
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < total.size(); i++){
                     ^
icc.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j = 0; j < aux[total[i]].size(); j++){
                       ^
icc.cpp:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int j = 0; j < aux[total[i]].size(); j++){
                       ^
icc.cpp:113:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < aux[b[0]].size(); i++){
                     ^
icc.cpp:121:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < aux[a[0]].size(); i++){
                     ^
icc.cpp:129:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < total.size(); i++){
                    ^
icc.cpp:133:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < total2.size(); i++){
                    ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2088 KB Ok! 105 queries used.
2 Correct 6 ms 2088 KB Ok! 102 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2088 KB Ok! 521 queries used.
2 Correct 53 ms 2088 KB Ok! 809 queries used.
3 Correct 56 ms 2088 KB Ok! 765 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 2084 KB Ok! 1459 queries used.
2 Correct 186 ms 2084 KB Ok! 2105 queries used.
3 Correct 126 ms 2088 KB Ok! 1533 queries used.
4 Correct 139 ms 2092 KB Ok! 1671 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 2084 KB Ok! 1592 queries used.
2 Correct 139 ms 2092 KB Ok! 1616 queries used.
3 Correct 163 ms 2084 KB Ok! 1880 queries used.
4 Correct 123 ms 2084 KB Ok! 1465 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 2084 KB Too many queries! 1849 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 2088 KB Too many queries! 1898 out of 1625
2 Halted 0 ms 0 KB -