oj.uz

Submission #210712

# Submission time Handle Problem Language Result Execution time Memory
210712 2020-03-18T06:37:24 Z bensonlzl ICC (CEOI16_icc) C++14
0 / 100
 25 ms 2424 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pi;

int s0, s1, a[105], b[105];

int par[105];
vector<int> sz[105];
int cnt[8], setbit;

void res(){
	for (int i = 0; i < 105; ++i){
		a[i] = b[i] = 0;
	}
	s0 = s1 = 0;
}

int query_v(vector<int> A, vector<int> B){
	res();
	for (int i = 0; i < A.size(); ++i){
		a[i] = A[i];
	}
	for (int i = 0; i < B.size(); ++i){
		b[i] = B[i];
	}
	return query(A.size(),B.size(),a,b);
}

pi solve(vector<int> A, vector<int> B){
	if (B.size() == 1){
		if (A.size() == 1){
			return pi(A[0],B[0]);
		}
		else return solve(B,A);
	}
	vector<int> b0, b1;
	for (int i = 0; i < B.size(); ++i){
		if (i%2 == 0) b0.push_back(B[i]);
		else b1.push_back(B[i]);
	}
	int q = query_v(A,b0);
	if (q) return solve(A,b0);
	else return solve(A,b1);
}

int find_par(int x){
	if (par[x] != x) par[x] = find_par(par[x]);
	return par[x];
}

void merg(int x, int y){
	int X = find_par(x), Y = find_par(y);
	if (X == Y) return;
	if (sz[X] < sz[Y]) swap(X,Y);
	for (auto it : sz[Y]){
		sz[X].push_back(it);
	}
	par[Y] = X;
}

vector<int> expand(vector<int> p){
	vector<int> r;
	for (auto it : p){
		for (auto it2 : sz[it]){
			r.push_back(it2);
		}
	}
	return r;
}



void run(int n) {
	for (int i = 1; i <= n; ++i){
		par[i] = i;
		sz[i].push_back(i);
	}
    for (int i = 1; i < n; ++i){
    	vector<int> pars;
    	for (int k = 1; k <= n; ++k){
    		pars.push_back(find_par(k));
    	}
    	sort(pars.begin(),pars.end());
    	pars.resize(unique(pars.begin(),pars.end())-pars.begin());
    	vector<int> v0, v1, ax, bx;
    	int check = 0;
    	for (int b = 0; b < 6; ++b){
    		v0.clear();
    		v1.clear();
    		ax.clear();
    		bx.clear();
    		for (int j = 0; j < pars.size(); ++j){
    			if (j & (1 << b)) v1.push_back(pars[j]);
    			else v0.push_back(pars[j]);
    		}
    		ax = expand(v0);
    		bx = expand(v1);
    		int q = query_v(v0,v1);
    		if (q){
    			check = 1;
    			break;
    		}
    	}
    	if (!check){
    		v0.clear();
    		v1.clear();
    		ax.clear();
    		bx.clear();
    		for (int j = 0; j < pars.size(); ++j){
    			if (j & (1 << 6)) v1.push_back(pars[j]);
    			else v0.push_back(pars[j]);
    		}
    		ax = expand(v0);
    		bx = expand(v1);
    	}
    	pi X = solve(ax,bx);
    	//cerr << X.first << ' ' << X.second << '\n';
    	setRoad(X.first,X.second);
    	merg(X.first,X.second);
    }
}

Compilation message

icc.cpp: In function 'int query_v(std::vector<int>, std::vector<int>)':
icc.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size(); ++i){
                  ~~^~~~~~~~~~
icc.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < B.size(); ++i){
                  ~~^~~~~~~~~~
icc.cpp: In function 'pi solve(std::vector<int>, std::vector<int>)':
icc.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < B.size(); ++i){
                  ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:94:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < pars.size(); ++j){
                       ~~^~~~~~~~~~~~~
icc.cpp:111:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < pars.size(); ++j){
                       ~~^~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1272 KB Number of queries more than 3000 out of 1500
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 2424 KB Number of queries more than 5000 out of 2500
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 504 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 504 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 552 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 504 KB Wrong road!
2 Halted 0 ms 0 KB -