oj.uz

Submission #211819

# Submission time Handle Problem Language Result Execution time Memory
211819 2020-03-21T12:48:18 Z bensonlzl ICC (CEOI16_icc) C++14
100 / 100
 170 ms 632 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
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){
	//cerr << A.size() << ' ' << B.size() << '\n';
	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].size() < sz[Y].size()) 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(ax,bx);
    		//cerr << b << ' ' << q << '\n';
    		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:24:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < A.size(); ++i){
                  ~~^~~~~~~~~~
icc.cpp:27: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:42: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:98:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < pars.size(); ++j){
                       ~~^~~~~~~~~~~~~
icc.cpp:117:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < pars.size(); ++j){
                       ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 512 KB Ok! 96 queries used.
2 Correct 11 ms 512 KB Ok! 100 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 512 KB Ok! 516 queries used.
2 Correct 58 ms 512 KB Ok! 667 queries used.
3 Correct 61 ms 512 KB Ok! 666 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 512 KB Ok! 1392 queries used.
2 Correct 160 ms 512 KB Ok! 1590 queries used.
3 Correct 147 ms 512 KB Ok! 1520 queries used.
4 Correct 165 ms 512 KB Ok! 1479 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 512 KB Ok! 1414 queries used.
2 Correct 163 ms 512 KB Ok! 1471 queries used.
3 Correct 156 ms 512 KB Ok! 1575 queries used.
4 Correct 153 ms 632 KB Ok! 1437 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 512 KB Ok! 1584 queries used.
2 Correct 159 ms 512 KB Ok! 1548 queries used.
3 Correct 166 ms 584 KB Ok! 1592 queries used.
4 Correct 164 ms 512 KB Ok! 1602 queries used.
5 Correct 152 ms 512 KB Ok! 1492 queries used.
6 Correct 159 ms 512 KB Ok! 1508 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 512 KB Ok! 1575 queries used.
2 Correct 148 ms 512 KB Ok! 1546 queries used.