Submission #301060

#	Time	Username	Problem	Language	Result	Execution time	Memory
301060		JPN20	Simurgh (IOI17_simurgh)	C++17	100 / 100	443 ms	14584 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

// Input
int N, M, Q;
int A[1 << 18], B[1 << 18];
int C[509][509];
int idxs[509][509];
int ret[509][509];

// DFS Tree
bool used[1 << 18];
bool istree[1 << 18];
int par[1 << 18];
int wei[1 << 18];
int cl[1 << 18], cr[1 << 18];
vector<int> ord;
vector<int> X[1 << 18];

// DFS Tree Base
int BASE = 0;
vector<int> R;

void dfs(int pos) {
	used[pos] = true;
	cl[pos] = ord.size();
	ord.push_back(pos);
	for (int i : X[pos]) {
		if (used[i] == true) continue;
		par[i] = pos;
		istree[idxs[pos][i]] = true;
		dfs(i);
	}
	cr[pos] = ord.size() - 1;
}

vector<int> find_roads(int n, vector<int> u, vector<int> v) {
	// INPUT
	N = n;
	M = u.size();
	for (int i = 0; i < M; i++) A[i] = u[i];
	for (int i = 0; i < M; i++) B[i] = v[i];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) idxs[i][j] = -1;
	}
	for (int i = 0; i < M; i++) idxs[A[i]][B[i]] = i;
	for (int i = 0; i < M; i++) idxs[B[i]][A[i]] = i;
	
	// DFSTR
	for (int i = 0; i < M; i++) X[A[i]].push_back(B[i]);
	for (int i = 0; i < M; i++) X[B[i]].push_back(A[i]);
	dfs(0);
	for (int i = 0; i < M; i++) {
		if (istree[i] == true) R.push_back(i);
	}
	BASE = count_common_roads(R); Q++;
	
	// PRTRH
	for (int i = 0; i < N; i++) wei[i] = -1;
	for (int i = 0; i < M; i++) {
		if (cl[A[i]] > cl[B[i]]) swap(A[i], B[i]);
		int cx = B[i];
		while (cx != A[i]) { C[A[i]][B[i]] = cx; C[B[i]][A[i]] = cx; cx = par[cx]; }
	}
	
	// TRHNT
	for (int i : ord) {
		if (i == 0 || wei[i] != -1) continue;
		int idx1 = -1;
		for (int j = 0; j < M; j++) {
			if (istree[j] == true) continue;
			if (!(cl[i] <= cl[B[j]] && cl[B[j]] <= cr[i])) continue;
			if (cl[par[i]] <= cl[A[j]]) continue;
			idx1 = j;
		}
		if (idx1 != -1) {
			int s0 = i, s1 = par[i], s2 = par[par[i]];
			vector<int> r1, r2;
			for (int j : R) { if (j != idxs[s0][s1]) r1.push_back(j); }
			for (int j : R) { if (j != idxs[s1][s2]) r2.push_back(j); }
			r1.push_back(idx1);
			r2.push_back(idx1);
			int p1 = count_common_roads(r1); Q++;
			int p2 = count_common_roads(r2); Q++;
			int eval = p2 - (BASE - wei[s1]);
			wei[i] = BASE - (p1 - eval);
		}
		else {
			int idx2 = -1, maxid = -1; vector<int> idx3;
			for (int j = 0; j < M; j++) {
				if (istree[j] == true) continue;
				if (!(cl[i] <= cl[B[j]] && cl[B[j]] <= cr[i])) continue;
				if (par[i] != A[j]) continue;
				idx3.push_back(j);
				if (maxid < cl[B[j]]) { maxid = cl[B[j]]; idx2 = j; }
			}
			if (idx2 != -1) {
				int cx = B[idx2];
				vector<pair<int, int>> vals;
				while (true) {
					vector<int> r;
					for (int j : R) { if (j != idxs[cx][par[cx]]) r.push_back(j); }
					r.push_back(idx2);
					vals.push_back(make_pair(cx, BASE - count_common_roads(r))); Q++;
					cx = par[cx];
					if (cx == A[idx2]) break;
				}
				int maxv = 0, minv = 0;
				for (int j = 0; j < (int)vals.size(); j++) maxv = max(maxv, vals[j].second);
				for (int j = 0; j < (int)vals.size(); j++) minv = min(minv, vals[j].second);
				for (int j = 0; j < (int)vals.size(); j++) wei[vals[j].first] = vals[j].second;
				if (maxv == 0 && minv == -1) {
					for (int j = 0; j < (int)vals.size(); j++) wei[vals[j].first] += 1;
				}
				if (maxv == 0 && minv == 0) {
					bool flg = false;
					for (int j : idx3) {
						vector<int> r;
						for (int k : R) { if (k != idxs[i][par[i]]) r.push_back(k); }
						r.push_back(j);
						int eval = BASE - count_common_roads(r); Q++;
						if (eval == -1) flg = true;
					}
					if (flg == false) {
						for (int j = 0; j < (int)vals.size(); j++) wei[vals[j].first] += 1;
					}
				}
			}
			else {
				wei[i] = 1;
			}
		}
	}
	
	// PRFNL
	for (int i = 1; i < N; i++) {
		ret[par[i]][i] = wei[i];
		ret[i][par[i]] = wei[i];
	}
	
	// FINAL
	for (int t = 2; t < ord.size(); t++) {
		int i = ord[t];
		vector<int> vec;
		for (int j = 0; j < M; j++) {
			if (istree[j] == true) continue;
			if (B[j] == i) vec.push_back(A[j]);
		}
		int cx = vec.size(), cnt = 0;
		while (cx >= 1) {
			if (true) {
				vector<int> r;
				vector<bool> uses(N, false);
				int ExpCost = BASE + cnt;
				for (int k = 0; k < (int)vec.size(); k++) r.push_back(idxs[vec[k]][i]);
				for (int k = 0; k < (int)vec.size(); k++) uses[C[vec[k]][i]] = true;
				for (int k = 1; k < N; k++) { if (uses[k] == true) ExpCost -= ret[k][par[k]]; }
				for (int k = 1; k < N; k++) { if (uses[k] == false) r.push_back(idxs[k][par[k]]); }
				int val = count_common_roads(r);
				if (val <= ExpCost) break;
			}
			int cl = 0, cr = cx, cm, maxn = -1;
			int pres = -1;
			for (int j = 0; j < 11; j++) {
				cm = (cl + cr) / 2;
				vector<int> r;
				vector<bool> uses(N, false);
				int ExpCost = BASE + cnt;
				for (int k = cm; k < (int)vec.size(); k++) r.push_back(idxs[vec[k]][i]);
				for (int k = cm; k < (int)vec.size(); k++) uses[C[vec[k]][i]] = true;
				for (int k = 1; k < N; k++) { if (uses[k] == true) ExpCost -= ret[k][par[k]]; }
				for (int k = 1; k < N; k++) { if (uses[k] == false) r.push_back(idxs[k][par[k]]); }
				int val = count_common_roads(r);
				if (val > ExpCost) { maxn = max(maxn, cm); cl = cm; }
				else { cr = cm; }
				if (pres == cm) break;
				pres = cm;
			}
			if (maxn == -1) break;
			cnt += 1;
			ret[i][vec[maxn]] = 1;
			ret[vec[maxn]][i] = 1;
			cx = maxn;
		}
	}
	
	// FLARE
	vector<int> FinalAns;
	for (int i = 0; i < M; i++) {
		if (ret[A[i]][B[i]] == 1) FinalAns.push_back(i);
	}
	return FinalAns;
}

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:143:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |  for (int t = 2; t < ord.size(); t++) {
      |                  ~~^~~~~~~~~~~~

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