oj.uz

Submission #444314

# Submission time Handle Problem Language Result Execution time Memory
444314 2021-07-13T15:15:58 Z keta_tsimakuridze ICC (CEOI16_icc) C++14
100 / 100
 152 ms 500 KB 
#include "icc.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=105,mod=1e9+7;
int fix[N],X,idx,n;
vector<pair<int,int> > edges;
vector<int> x,y,V[N],comp[N];
int solve(vector<int> x, vector<int> y){
	int l = 0, r = (int)x.size() - 1, u;
	while(l < r) {
		int mid = (l+r)/2; 
		int x1[mid+1],y1[y.size()];
		for(int i = 0; i<=mid; i++) {
			x1[i] = x[i];	 
		} 
		for(int i = 0; i<y.size(); i++) {
			y1[i] = y[i];
		}
		int f = query(mid+1,y.size(),x1,y1);
		if(f) { 
			r = mid;
		}
		else {
			l = mid + 1;
		}
	}
	return x[r];
}
void dfs(int u,int cur) {
	comp[cur].push_back(u);
	fix[u] = 1;
	for(int i=0;i<V[u].size();i++) {
		if(!fix[V[u][i]]) dfs(V[u][i],cur);
	}
}
void in(vector<int> &x,int cur){
	for(int i = 0; i<comp[cur].size();i++){
		x.push_back(comp[cur][i]);
	}
}
void run(int m){
	n = m;
	int lft = n - 1;
	X = -1;
	while(lft-- ){
		X++;
		for(int i=1;i<=n;i++) fix[i] = 0;
		int cur = 0;
		idx = 0;
		for(int i=1;i<=n;i++) {
			if(!fix[i]) {
				comp[cur] .clear();
				dfs(i,cur++);
			}
		}			
		vector<int> x,y;
		for(int i=0; i<=log2(cur-1);i++) {
			x.clear(); y.clear();
			for(int j=0;j<cur;j++) {
				if(j & (1<<i)) {
					in(x,j);
				}
				else in(y,j);
			}
			int x1[x.size()],y1[y.size()];
			for(int i = 0; i<x.size(); i++) x1[i] = x[i];
			for(int i = 0; i<y.size(); i++) y1[i] = y[i];
			if(query(x.size(),y.size(),x1,y1)) break;
		}
		int u = solve(x,y);
		int v = solve(y,x); 
		setRoad(u,v);
		V[u].push_back(v);
		V[v].push_back(u);
	}
}

Compilation message

icc.cpp: In function 'int solve(std::vector<int>, std::vector<int>)':
icc.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i = 0; i<y.size(); i++) {
      |                  ~^~~~~~~~~
icc.cpp:11:36: warning: unused variable 'u' [-Wunused-variable]
   11 |  int l = 0, r = (int)x.size() - 1, u;
      |                                    ^
icc.cpp: In function 'void dfs(int, int)':
icc.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=0;i<V[u].size();i++) {
      |              ~^~~~~~~~~~~~
icc.cpp: In function 'void in(std::vector<int>&, int)':
icc.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0; i<comp[cur].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |    for(int i = 0; i<x.size(); i++) x1[i] = x[i];
      |                   ~^~~~~~~~~
icc.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    for(int i = 0; i<y.size(); i++) y1[i] = y[i];
      |                   ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 496 KB Ok! 95 queries used.
2 Correct 8 ms 492 KB Ok! 98 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 460 KB Ok! 526 queries used.
2 Correct 42 ms 496 KB Ok! 653 queries used.
3 Correct 44 ms 480 KB Ok! 636 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 480 KB Ok! 1379 queries used.
2 Correct 152 ms 500 KB Ok! 1593 queries used.
3 Correct 133 ms 488 KB Ok! 1593 queries used.
4 Correct 134 ms 460 KB Ok! 1481 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 480 KB Ok! 1424 queries used.
2 Correct 131 ms 460 KB Ok! 1452 queries used.
3 Correct 142 ms 480 KB Ok! 1575 queries used.
4 Correct 131 ms 484 KB Ok! 1493 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 484 KB Ok! 1540 queries used.
2 Correct 136 ms 496 KB Ok! 1515 queries used.
3 Correct 144 ms 460 KB Ok! 1573 queries used.
4 Correct 138 ms 492 KB Ok! 1525 queries used.
5 Correct 132 ms 492 KB Ok! 1442 queries used.
6 Correct 139 ms 484 KB Ok! 1478 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 480 KB Ok! 1538 queries used.
2 Correct 146 ms 496 KB Ok! 1588 queries used.