Submission #444314

#	Time	Username	Problem	Language	Result	Execution time	Memory
444314		keta_tsimakuridze	ICC (CEOI16_icc)	C++14	100 / 100	152 ms	500 KiB

icc

#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 (stderr)

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10