oj.uz

Submission #134185

# Submission time Handle Problem Language Result Execution time Memory
134185 2019-07-22T08:10:00 Z ekrem ICC (CEOI16_icc) C++
18 / 100
 421 ms 24204 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];
vector < int > g[N];

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(x[0], 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(query(aa, bb, a, b))
			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(query(aa, bb, a, b))
			coz2(x, bir);
		else
			coz2(x, iki);
	}
}

void coz(vi x){
	if(fl or (int)x.size() <= 1)
		return;
	int sz = x.size();
	aa = 0;
	bb = 0;
	vi bir, iki, birr, ikii;
	for(int i = 0; i < sz/2; i++){
		bir.pb(x[i]);
		for(int j = 0; j < g[x[i]].size(); j++){
			a[aa++] = g[x[i]][j];
			birr.pb(g[x[i]][j]);
		}
	}
	for(int i = sz/2; i < sz; i++){
		iki.pb(x[i]);
		for(int j = 0; j < g[x[i]].size(); j++){
			b[bb++] = g[x[i]][j];
			ikii.pb(g[x[i]][j]);
		}
	}
	if(query(aa, bb, a, b)){
		coz2(birr, ikii);
		fl = 1;
		return;
	}
	coz(bir);
	coz(iki);
}


void run(int nn){n = nn;
	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:28: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:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < y.size(); i++)
                  ~~^~~~~~~~~~
icc.cpp:65: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:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < g[x[i]].size(); j++){
                  ~~^~~~~~~~~~~~~~~~
icc.cpp:90:20: 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 30 ms 24056 KB Ok! 104 queries used.
2 Correct 30 ms 24188 KB Ok! 107 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 24056 KB Ok! 1037 queries used.
2 Correct 132 ms 24056 KB Ok! 1445 queries used.
3 Correct 124 ms 24188 KB Ok! 1456 queries used.

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 421 ms 24200 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 380 ms 24204 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 336 ms 24084 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 319 ms 24112 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -