제출 #432079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
432079		rainboy	Simurgh (IOI17_simurgh)	C++98	51 / 100	135 ms	3348 KiB

simurgh

#include "simurgh.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

const int N = 240, M = N * (N - 1) / 2;

typedef vector<int> vi;

int ds[N], n;

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

int join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}

int ii[M], jj[M];
int *eh[N], eo[N];

void append(int i, int h) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

char cc[M], marked[M];

int dfs(int p, int i, int t) {
	int o;

	if (i == t)
		return 1;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ii[h] ^ jj[h];

		if (j != p && dfs(i, j, t)) {
			marked[h] = 1;
			return 1;
		}
	}
	return 0;
}

vi hh, hh_;
int k_;

int count(int i, int m) {
	int g, m_, k;

	memset(ds, -1, n * sizeof *ds);
	m_ = 0;
	for (g = 0; g < m; g++) {
		int h = eh[i][g];

		join(ii[h], jj[h]);
		hh_[m_++] = h;
	}
	k = 0;
	for (g = 0; g < n - 1; g++)
		if (join(ii[hh[g]], jj[hh[g]]))
			hh_[m_++] = hh[g];
		else if (cc[hh[g]])
			k++;
	return count_common_roads(hh_) - k_ + k;
}

void solve(int i, int l, int r, int a, int b) {
	int m, c;

	if (a == b)
		return;
	if (r - l == 1) {
		cc[eh[i][l]] = 1;
		return;
	}
	m = (l + r) / 2;
	c = count(i, m);
	solve(i, l, m, a, c), solve(i, m, r, c, b);
}

vi find_roads(int n_, vi ii_, vi jj_) {
	int m = ii_.size(), m_, g, h, i;

	n = n_;
	for (h = 0; h < m; h++)
		ii[h] = ii_[h], jj[h] = jj_[h];
	hh.resize(n - 1), hh_.resize(n - 1);
	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	m_ = 0;
	for (h = 0; h < m; h++)
		if (join(ii[h], jj[h])) {
			hh[m_++] = h, cc[h] = -1;
			append(ii[h], h), append(jj[h], h);
		} else
			cc[h] = -2;
	k_ = count_common_roads(hh);
	for (h = 0; h < m; h++) {
		int upd, c, tmp, k;

		if (cc[h] != -2)
			continue;
		for (g = 0; g < n - 1; g++)
			marked[hh[g]] = 0;
		dfs(-1, ii[h], jj[h]);
		upd = 0;
		for (g = 0; g < n - 1; g++)
			if (marked[hh[g]] && cc[hh[g]] == -1) {
				upd = 1;
				break;
			}
		if (!upd)
			continue;
		c = -1;
		for (g = 0; g < n - 1; g++)
			if (marked[hh[g]] && cc[hh[g]] != -1) {
				tmp = hh[g], hh[g] = h, k = count_common_roads(hh), hh[g] = tmp;
				c = cc[hh[g]] ^ (k == k_ ? 0 : 1);
				break;
			}
		for (g = 0; g < n - 1; g++)
			if (marked[hh[g]] && cc[hh[g]] == -1) {
				tmp = hh[g], hh[g] = h, k = count_common_roads(hh), hh[g] = tmp;
				if (k == k_ + 1)
					c = 1;
				else if (k == k_ - 1)
					c = 0;
				if (c != -1)
					cc[hh[g]] = c ^ (k == k_ ? 0 : 1);
			}
		if (c == -1)
			c = 0;
		for (g = 0; g < n - 1; g++)
			if (marked[hh[g]] && cc[hh[g]] == -1)
				cc[hh[g]] = c;
	}
	for (h = 0; h < m; h++)
		if (cc[h] == -1)
			cc[h] = 1;
		else if (cc[h] == -2)
			append(ii[h], h), append(jj[h], h);
	for (i = 0; i < n; i++) {
		int o, o_;

		for (o = 0, o_ = 0; o < eo[i]; o++) {
			h = eh[i][o];
			if (cc[h] == -2)
				cc[h] = 0, eh[i][o_++] = h;
		}
		eo[i] = o_;
		solve(i, 0, eo[i], 0, count(i, eo[i]));
	}
	m_ = 0;
	for (h = 0; h < m; h++)
		if (cc[h] == 1)
			hh[m_++] = h;
	return hh;
}

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

simurgh.cpp: In function 'void append(int, int)':
simurgh.cpp:39:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   39 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30