oj.uz

Submission #300988

# Submission time Handle Problem Language Result Execution time Memory
300988 2020-09-17T15:42:22 Z JPN20 Simurgh (IOI17_simurgh) C++17
13 / 100
 219 ms 11820 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

// Input
int N, M;
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);
	
	// 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) {
			//cout << "# "<< i << ": " << idx1 << endl;
			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);
			int p2 = count_common_roads(r2);
			int eval = p2 - (BASE - wei[s1]);
			wei[i] = BASE - (p1 - eval);
		}
		else {
			int idx2 = -1, maxid = -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 (par[i] != A[j]) continue;
				if (maxid < cl[B[j]]) { maxid = cl[B[j]]; idx2 = j; }
			}
			if (idx2 != -1) {
				//cout << "! " << i << ": " << idx2 << endl;
				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)));
					cx = par[cx];
					if (cx == A[idx2]) break;
				}
				int maxv = 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++) wei[vals[j].first] = vals[j].second;
				if (maxv == 0) {
					for (int j = 0; j < (int)vals.size(); j++) wei[vals[j].first] += 1;
				}
			}
			else {
				//cout << "? " << i << endl;
				wei[i] = 1;
			}
		}
	}
	
	// PRFNL
	for (int i = 1; i < N; i++) {
		ret[par[i]][i] = wei[i];
		ret[i][par[i]] = wei[i];
	}
	//for (int i = 1; i < N; i++) cout << i << ": " << wei[i] << endl;
	
	// 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) {
			int cl = 0, cr = cx, cm, maxn = -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 < vec.size(); k++) r.push_back(idxs[vec[k]][i]);
				for (int k = cm; k < 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 (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

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:132:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |  for (int t = 2; t < ord.size(); t++) {
      |                  ~~^~~~~~~~~~~~
simurgh.cpp:147:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for (int k = cm; k < vec.size(); k++) r.push_back(idxs[vec[k]][i]);
      |                      ~~^~~~~~~~~~~~
simurgh.cpp:148:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for (int k = cm; k < vec.size(); k++) uses[C[vec[k]][i]] = true;
      |                      ~~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB correct
2 Correct 5 ms 6528 KB correct
3 Correct 5 ms 6528 KB correct
4 Correct 6 ms 6528 KB correct
5 Correct 5 ms 6528 KB correct
6 Correct 5 ms 6528 KB correct
7 Correct 5 ms 6528 KB correct
8 Correct 5 ms 6528 KB correct
9 Correct 4 ms 6528 KB correct
10 Correct 5 ms 6528 KB correct
11 Correct 4 ms 6528 KB correct
12 Correct 5 ms 6528 KB correct
13 Correct 5 ms 6528 KB correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB correct
2 Correct 5 ms 6528 KB correct
3 Correct 5 ms 6528 KB correct
4 Correct 6 ms 6528 KB correct
5 Correct 5 ms 6528 KB correct
6 Correct 5 ms 6528 KB correct
7 Correct 5 ms 6528 KB correct
8 Correct 5 ms 6528 KB correct
9 Correct 4 ms 6528 KB correct
10 Correct 5 ms 6528 KB correct
11 Correct 4 ms 6528 KB correct
12 Correct 5 ms 6528 KB correct
13 Correct 5 ms 6528 KB correct
14 Correct 8 ms 6912 KB correct
15 Correct 8 ms 6912 KB correct
16 Correct 8 ms 6912 KB correct
17 Correct 8 ms 6912 KB correct
18 Correct 7 ms 6912 KB correct
19 Incorrect 30 ms 6912 KB WA in grader: NO
20 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB correct
2 Correct 5 ms 6528 KB correct
3 Correct 5 ms 6528 KB correct
4 Correct 6 ms 6528 KB correct
5 Correct 5 ms 6528 KB correct
6 Correct 5 ms 6528 KB correct
7 Correct 5 ms 6528 KB correct
8 Correct 5 ms 6528 KB correct
9 Correct 4 ms 6528 KB correct
10 Correct 5 ms 6528 KB correct
11 Correct 4 ms 6528 KB correct
12 Correct 5 ms 6528 KB correct
13 Correct 5 ms 6528 KB correct
14 Correct 8 ms 6912 KB correct
15 Correct 8 ms 6912 KB correct
16 Correct 8 ms 6912 KB correct
17 Correct 8 ms 6912 KB correct
18 Correct 7 ms 6912 KB correct
19 Incorrect 30 ms 6912 KB WA in grader: NO
20 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB correct
2 Correct 5 ms 6656 KB correct
3 Incorrect 219 ms 11820 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6528 KB correct
2 Correct 5 ms 6528 KB correct
3 Correct 5 ms 6528 KB correct
4 Correct 6 ms 6528 KB correct
5 Correct 5 ms 6528 KB correct
6 Correct 5 ms 6528 KB correct
7 Correct 5 ms 6528 KB correct
8 Correct 5 ms 6528 KB correct
9 Correct 4 ms 6528 KB correct
10 Correct 5 ms 6528 KB correct
11 Correct 4 ms 6528 KB correct
12 Correct 5 ms 6528 KB correct
13 Correct 5 ms 6528 KB correct
14 Correct 8 ms 6912 KB correct
15 Correct 8 ms 6912 KB correct
16 Correct 8 ms 6912 KB correct
17 Correct 8 ms 6912 KB correct
18 Correct 7 ms 6912 KB correct
19 Incorrect 30 ms 6912 KB WA in grader: NO
20 Halted 0 ms 0 KB -