제출 #134247

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134247		ekrem	ICC (CEOI16_icc)	C++98	90 / 100	282 ms	24184 KiB

icc

#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);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 0 / 10