oj.uz

Submission #115231

# Submission time Handle Problem Language Result Execution time Memory
115231 2019-06-06T08:06:01 Z sebinkim ICC (CEOI16_icc) C++14
100 / 100
 155 ms 760 KB 
#include <bits/stdc++.h>

#include "icc.h"

using namespace std;

vector <int> V[111], Z;
int P[111], K[111];
int X[111], Y[111];
int x, y;

int find(int p) { return p == P[p]? p : P[p] = find(P[p]); }
void unite(int p, int q) { P[find(p)] = find(q); }

void run(int n)
{
	int i, j, k, t, b, m, s, e, u, v, p, q;
	
	for(i=0; i<n; i++){
		P[i] = i;
	}
	
	for(i=1; i<n; i++){
		for(j=0; j<n; j++){
			V[j].clear();
		}
		
		for(j=0, k=0; j<n; j++){
			if(find(j) == j) K[k ++] = j;
			V[find(j)].push_back(j);
		}
		
		for(t=0, b=0; (1 << t) < k; t++){
			x = 0, y = 0;
			for(j=0; j<k; j++){
				if(j & (1 << t)){
					for(int &v: V[K[j]]) X[x ++] = v + 1;
				}
				else{
					for(int &v: V[K[j]]) Y[y ++] = v + 1;
				}
			}
			
			if(query(x, y, X, Y)){
				b |= 1 << t;
			}
		}
		
		Z.clear();
		
		for(j=0; j<k; j++){
			if((j ^ b) < k && j < (j ^ b)){
				Z.push_back(j);
			}
		}
		
		for(s=0, e=Z.size()-2; s<=e; ){
			m = s + e >> 1;
			x = 0; y = 0;
			for(j=0; j<=m; j++){
				for(int &v: V[K[Z[j]]]) X[x ++] = v + 1;
				for(int &v: V[K[Z[j] ^ b]]) Y[y ++] = v + 1;
			}
			if(query(x, y, X, Y)) e = m - 1;
			else s = m + 1;
		}
		
		p = K[Z[e + 1]]; q = K[Z[e + 1] ^ b];
		
		y = 0;
		for(int &v: V[q]) Y[y ++] = v + 1;
		
		for(s=0, e=V[p].size()-2; s<=e; ){
			m = s + e >> 1;
			x = 0;
			for(j=0; j<=m; j++){
				X[x ++] = V[p][j] + 1;
			}
			if(query(x, y, X, Y)) e = m - 1;
			else s = m + 1;
		}
		
		u = V[p][e + 1];
		
		y = 0;
		for(int &v: V[p]) Y[y ++] = v + 1;
		
		for(s=0, e=V[q].size()-2; s<=e; ){
			m = s + e >> 1;
			x = 0;
			for(j=0; j<=m; j++){
				X[x ++] = V[q][j] + 1;
			}
			if(query(x, y, X, Y)) e = m - 1;
			else s = m + 1;
		}
		
		v = V[q][e + 1];
		
		setRoad(u + 1, v + 1);
		unite(u, v);
	}
}

Compilation message

icc.cpp: In function 'void run(int)':
icc.cpp:58:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    m = s + e >> 1;
        ~~^~~
icc.cpp:74:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    m = s + e >> 1;
        ~~^~~
icc.cpp:89:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    m = s + e >> 1;
        ~~^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 640 KB Ok! 110 queries used.
2 Correct 7 ms 512 KB Ok! 105 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 512 KB Ok! 603 queries used.
2 Correct 37 ms 512 KB Ok! 571 queries used.
3 Correct 42 ms 512 KB Ok! 609 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 512 KB Ok! 1520 queries used.
2 Correct 125 ms 636 KB Ok! 1493 queries used.
3 Correct 131 ms 512 KB Ok! 1493 queries used.
4 Correct 130 ms 512 KB Ok! 1480 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 572 KB Ok! 1470 queries used.
2 Correct 133 ms 632 KB Ok! 1468 queries used.
3 Correct 117 ms 512 KB Ok! 1493 queries used.
4 Correct 126 ms 512 KB Ok! 1507 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 512 KB Ok! 1487 queries used.
2 Correct 130 ms 688 KB Ok! 1492 queries used.
3 Correct 121 ms 512 KB Ok! 1490 queries used.
4 Correct 155 ms 760 KB Ok! 1487 queries used.
5 Correct 126 ms 512 KB Ok! 1479 queries used.
6 Correct 128 ms 512 KB Ok! 1467 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 640 KB Ok! 1492 queries used.
2 Correct 125 ms 512 KB Ok! 1493 queries used.