oj.uz

Submission #134247

# Submission time Handle Problem Language Result Execution time Memory
134247 2019-07-22T09:14:19 Z ekrem ICC (CEOI16_icc) C++
90 / 100
 282 ms 24184 KB 
#include "icc.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define N 1000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;
typedef vector < int > vi;


int n, fl, ata[N], aa, bb, a[N], b[N], of[N];
vector < int > g[N];

int sor(){
	for(int i = 0; i < aa; i++)
		a[i] = of[a[i]];
	for(int i = 0; i < bb; i++)
		b[i] = of[b[i]];
	return query(aa, bb, a, b);
}

void merge(int i, int j){
	i = ata[i];
	j = ata[j];
	for(int x = 0; x < g[j].size(); x++){
		ata[g[j][x]] = i;
		g[i].pb(g[j][x]);
	}
}

void coz2(vi x, vi y){
	if((int)x.size() == 1 and (int)y.size() == 1){
		setRoad(of[x[0]], of[y[0]]);
		merge(x[0], y[0]);
		// cout << x[0] << " " << y[0] << endl;
		return;
	}
	aa = bb = 0;
	vi bir, iki;
	if((int)y.size() == 1){
		int sz = x.size();
		for(int i = 0; i < sz/2; i++){
			bir.pb(x[i]);
			a[aa++] = x[i];
		}
		for(int i = sz/2; i < sz; i++)
			iki.pb(x[i]);
		for(int i = 0; i < y.size(); i++)
			b[bb++] = y[i];
		if(sor())
			coz2(bir, y);
		else
			coz2(iki, y);
	} else{
		int sz = y.size();
		for(int i = 0; i < sz/2; i++){
			bir.pb(y[i]);
			a[aa++] = y[i];
		}
		for(int i = sz/2; i < sz; i++)
			iki.pb(y[i]);
		for(int i = 0; i < x.size(); i++)
			b[bb++] = x[i];
		if(sor())
			coz2(x, bir);
		else
			coz2(x, iki);
	}
}

void coz(vi x){
	for(int j = 0; j < 10; j++){
		int sz = x.size();
		aa = 0;
		bb = 0;
		vi bir, iki;
		for(int i = 0; i < sz; i++)
			if(i&(1<<j)){
				for(int j = 0; j < g[x[i]].size(); j++){
					a[aa++] = g[x[i]][j];
					bir.pb(g[x[i]][j]);
				}
			} else{
				for(int j = 0; j < g[x[i]].size(); j++){
					b[bb++] = g[x[i]][j];
					iki.pb(g[x[i]][j]);
				}
			}
		if(sor()){
			coz2(bir, iki);
			return;
		}

	}
}

int myrandom(int x){
	return rand()%x;
}

void run(int nn){n = nn;
	srand(time(0));

	for(int i = 1; i <= n; i++)
		of[i] = i;
	random_shuffle(of + 1, of + n + 1, myrandom);

	for(int i = 1; i <= n; i++){
		ata[i] = i;
		g[i].pb(i);
	}
	for(int i = 1; i < n; i++){
		vi x;
		for(int i = 1; i <= n; i++)
			if(ata[i] == i)
				x.pb(i);
		fl = 0;
		coz(x);
	}
}

Compilation message

icc.cpp: In function 'void merge(int, int)':
icc.cpp:36:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int x = 0; x < g[j].size(); x++){
                 ~~^~~~~~~~~~~~~
icc.cpp: In function 'void coz2(vi, vi)':
icc.cpp:59:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < y.size(); i++)
                  ~~^~~~~~~~~~
icc.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < x.size(); i++)
                  ~~^~~~~~~~~~
icc.cpp: In function 'void coz(vi)':
icc.cpp:90:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < g[x[i]].size(); j++){
                    ~~^~~~~~~~~~~~~~~~
icc.cpp:95:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < g[x[i]].size(); j++){
                    ~~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 24056 KB Ok! 94 queries used.
2 Correct 35 ms 24056 KB Ok! 104 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 24056 KB Ok! 535 queries used.
2 Correct 74 ms 24056 KB Ok! 691 queries used.
3 Correct 73 ms 24056 KB Ok! 694 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 24092 KB Ok! 1452 queries used.
2 Correct 180 ms 24092 KB Ok! 1704 queries used.
3 Correct 171 ms 24088 KB Ok! 1584 queries used.
4 Correct 168 ms 24184 KB Ok! 1537 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 24156 KB Ok! 1473 queries used.
2 Correct 163 ms 24056 KB Ok! 1491 queries used.
3 Correct 176 ms 24088 KB Ok! 1614 queries used.
4 Correct 164 ms 24184 KB Ok! 1498 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 24088 KB Ok! 1617 queries used.
2 Correct 179 ms 24092 KB Ok! 1614 queries used.
3 Correct 177 ms 24056 KB Ok! 1614 queries used.
4 Correct 282 ms 24184 KB Ok! 1630 queries used.
5 Correct 164 ms 24056 KB Ok! 1496 queries used.
6 Correct 178 ms 24088 KB Ok! 1562 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 24088 KB Ok! 1614 queries used.
2 Incorrect 182 ms 24184 KB Too many queries! 1704 out of 1625