Submission #444278

#	Time	Username	Problem	Language	Result	Execution time	Memory
444278		keta_tsimakuridze	ICC (CEOI16_icc)	C++14	0 / 100	6 ms	5196 KiB

icc

#include "icc.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7;
int comp[N],fix[N],X,idx,n;
vector<pair<int,int> > edges;
vector<int> a,x,y,V[N];
int solve(){
	int l = 0, r = n-1, u;
	while(l<=r) {
		int mid = (l+r)/2; 
		vector<int> x,y;
		for(int i = 0; i<=mid; i++) {
			x.push_back(a[i]);
		} 
		for(int i = mid+1; i<n; i++) {
			if(comp[a[i]] != comp[a[mid]]) y.push_back(a[i]);
		}
		if(!y.size()) {
			r = mid - 1;
			continue;
		}
		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];
		}
		int f = query(x.size(),y.size(),x1,y1);
		if(f) {
			r = mid - 1; 
			u = a[mid];
		}
		else {
			l = mid + 1;
		}
	}
	return u;
}

void dfs(int u,int cur) {
	idx++;
	a.push_back(u);
	comp[u] = cur;
	fix[u] = 1;
	for(int i=0;i<V[u].size();i++) {
		if(!fix[V[u][i]]) dfs(V[u][i],cur);
	}
}
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;
		a.clear();
		idx = 0;
		for(int i=1;i<=n;i++) {
			if(!fix[i]) {
				dfs(i,++cur);
			}
		}		
		int l = 1, r = n-1,u = 0,v = 0;
		u = solve();
		reverse(a.begin(),a.end());
		v = solve();
		V[u].push_back(v);
		V[v].push_back(u);
		setRoad(u,v);	 
	
	
	}
}

Compilation message (stderr)

icc.cpp: In function 'int solve()':
icc.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for(int i = 0; i<x.size(); i++) {
      |                  ~^~~~~~~~~
icc.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int i = 0; i<y.size(); i++) {
      |                  ~^~~~~~~~~
icc.cpp: In function 'void dfs(int, int)':
icc.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0;i<V[u].size();i++) {
      |              ~^~~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:68:7: warning: unused variable 'l' [-Wunused-variable]
   68 |   int l = 1, r = n-1,u = 0,v = 0;
      |       ^
icc.cpp:68:14: warning: unused variable 'r' [-Wunused-variable]
   68 |   int l = 1, r = n-1,u = 0,v = 0;
      |              ^
icc.cpp: In function 'int solve()':
icc.cpp:41:9: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |  return u;
      |         ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 21
• Subtask 5: 0 / 29
• Subtask 6: 0 / 10