oj.uz

Submission #291907

# Submission time Handle Problem Language Result Execution time Memory
291907 2020-09-06T01:51:02 Z Diuven ROI16_sending (ROI16_sending) C++11
100 / 100
 2584 ms 212192 KB 
#include <cassert>
#include <cstdio>
#include <set>
#include <vector>
#define mp make_pair
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) (a).size())
#define data __data
using namespace std;

const int L = 19;
const int N = (int) 2e5 + 10;
int n, m, curt, u, v, opt = 0, opti = 0, optj = 1, h[N], firstoc[N], order[2 * N], p[2 * N][L], mx[2 * N], curpos;
vector<int> adj[N];
typedef pair<int, int> tpath;
vector<tpath> paths[N], die[N];

struct cmp {
	bool operator()(tpath a, tpath b) {
		return (mp(firstoc[a.fs], a.sc) < mp(firstoc[b.fs], b.sc));
	}
};

typedef set< tpath, cmp > tpathset;
tpathset data[N];

void dfs(int v, int pv = -1) {
	firstoc[v] = curpos;
	order[curpos++] = v;
	for (int u : adj[v]) {
		if (u != pv) {
			h[u] += h[v];
			dfs(u, v);
			order[curpos++] = v;
		}
	}
}

int plusik(int a, int b) {
	return (h[a] < h[b]) ? a : b;
}

int lca(int u, int v) {
	u = firstoc[u], v = firstoc[v];
	if (u > v) {
		swap(u, v);
	}
	int k = mx[v - u + 1];
	return plusik(p[u][k], p[v - (1 << k) + 1][k]);
}

void relax(int v, tpath path1, tpath path2) {
	int res = h[v] - h[lca(v, path1.fs)] - h[lca(v, path2.fs)] + h[lca(path1.fs, path2.fs)];
	if (res > opt) {
		opt = res, opti = path1.sc, optj = path2.sc;
	}
}

void add(int v, tpath path) {
	auto match = data[v].lower_bound(path);
	if (match != data[v].end()) {
		relax(v, path, *match);
	}
	if (match != data[v].begin()) {
		relax(v, path, *(--match));
	}
	data[v].insert(path);
}

void solve(int v, int pv = -1) {
	for (int u : adj[v]) {
		if (u != pv) {
			solve(u, v);
			if (sz(data[v]) < sz(data[u])) {
				data[v].swap(data[u]);
			}
			for (tpath path : data[u]) {
				add(v, path);
			}
		}
	}
	for (tpath path : paths[v]) {
		add(v, path);
	}
	for (tpath path : die[v]) {
		data[v].erase(path);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n; ++i) {
		scanf("%d", &u), --u;
		adj[u].pb(i), adj[i].pb(u);
	}
	for (int i = 1; i < n; ++i)
		h[i] = 1;
	dfs(0, -1);
	mx[1] = 0;
	for (int i = 2; i < curpos; ++i) {
		mx[i] = mx[i - 1];
		if (i == (1 << (mx[i] + 1))) {
			mx[i]++;
		}
	}
	for (int i = 0; i < curpos; ++i)
		p[i][0] = order[i];
	for (int j = 1; j < L; ++j)
		for (int i = 0; i + (1 << j) <= curpos; ++i) {
			p[i][j] = plusik(p[i][j - 1], p[i + (1 << (j - 1))][j - 1]);
		}
	for (int i = 0; i < m; ++i) {
		scanf("%d%d", &u, &v), --u, --v;
		paths[u].pb(mp(v, i)), paths[v].pb(mp(u, i));
		int w = lca(u, v);
		die[w].pb(mp(v, i)), die[w].pb(mp(u, i));
	}
	solve(0, -1);
	printf("%d\n%d %d\n", opt, opti + 1, optj + 1);
	return 0;
}

Compilation message

sending.cpp: In function 'int main()':
sending.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
sending.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |   scanf("%d", &u), --u;
      |   ~~~~~^~~~~~~~~~
sending.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |   scanf("%d%d", &u, &v), --u, --v;
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23808 KB Output is correct
2 Correct 15 ms 23808 KB Output is correct
3 Correct 16 ms 23936 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 16 ms 23808 KB Output is correct
6 Correct 16 ms 23808 KB Output is correct
7 Correct 15 ms 23792 KB Output is correct
8 Correct 16 ms 23808 KB Output is correct
9 Correct 14 ms 23808 KB Output is correct
10 Correct 16 ms 23808 KB Output is correct
11 Correct 17 ms 23808 KB Output is correct
12 Correct 15 ms 23908 KB Output is correct
13 Correct 15 ms 23808 KB Output is correct
14 Correct 17 ms 23904 KB Output is correct
15 Correct 15 ms 23808 KB Output is correct
16 Correct 15 ms 23808 KB Output is correct
17 Correct 20 ms 23808 KB Output is correct
18 Correct 16 ms 23808 KB Output is correct
19 Correct 17 ms 23808 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24960 KB Output is correct
2 Correct 23 ms 24960 KB Output is correct
3 Correct 18 ms 25192 KB Output is correct
4 Correct 19 ms 24960 KB Output is correct
5 Correct 18 ms 24960 KB Output is correct
6 Correct 21 ms 24960 KB Output is correct
7 Correct 23 ms 25284 KB Output is correct
8 Correct 22 ms 25016 KB Output is correct
9 Correct 24 ms 25088 KB Output is correct
10 Correct 20 ms 25208 KB Output is correct
11 Correct 23 ms 25216 KB Output is correct
12 Correct 18 ms 25236 KB Output is correct
13 Correct 20 ms 25216 KB Output is correct
14 Correct 23 ms 25208 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 44712 KB Output is correct
2 Correct 126 ms 44688 KB Output is correct
3 Correct 99 ms 56836 KB Output is correct
4 Correct 96 ms 50588 KB Output is correct
5 Correct 94 ms 50552 KB Output is correct
6 Correct 76 ms 44780 KB Output is correct
7 Correct 110 ms 56828 KB Output is correct
8 Correct 83 ms 45180 KB Output is correct
9 Correct 98 ms 44624 KB Output is correct
10 Correct 111 ms 55624 KB Output is correct
11 Correct 103 ms 55492 KB Output is correct
12 Correct 99 ms 55544 KB Output is correct
13 Correct 108 ms 55544 KB Output is correct
14 Correct 96 ms 45944 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 46460 KB Output is correct
2 Correct 166 ms 46700 KB Output is correct
3 Correct 115 ms 57284 KB Output is correct
4 Correct 113 ms 51168 KB Output is correct
5 Correct 110 ms 51168 KB Output is correct
6 Correct 96 ms 45808 KB Output is correct
7 Correct 107 ms 57224 KB Output is correct
8 Correct 103 ms 46712 KB Output is correct
9 Correct 138 ms 47176 KB Output is correct
10 Correct 113 ms 56116 KB Output is correct
11 Correct 107 ms 55928 KB Output is correct
12 Correct 102 ms 55800 KB Output is correct
13 Correct 116 ms 56056 KB Output is correct
14 Correct 131 ms 55544 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 68728 KB Output is correct
2 Correct 544 ms 67596 KB Output is correct
3 Correct 543 ms 68944 KB Output is correct
4 Correct 508 ms 67180 KB Output is correct
5 Correct 378 ms 67832 KB Output is correct
6 Correct 538 ms 67692 KB Output is correct
7 Correct 547 ms 68968 KB Output is correct
8 Correct 512 ms 67180 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 52860 KB Output is correct
2 Correct 311 ms 53880 KB Output is correct
3 Correct 232 ms 60920 KB Output is correct
4 Correct 213 ms 54264 KB Output is correct
5 Correct 237 ms 55800 KB Output is correct
6 Correct 219 ms 54000 KB Output is correct
7 Correct 247 ms 60920 KB Output is correct
8 Correct 227 ms 54260 KB Output is correct
9 Correct 239 ms 55032 KB Output is correct
10 Correct 194 ms 62944 KB Output is correct
11 Correct 120 ms 60152 KB Output is correct
12 Correct 122 ms 60152 KB Output is correct
13 Correct 292 ms 61304 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 67556 KB Output is correct
2 Correct 491 ms 70124 KB Output is correct
3 Correct 246 ms 61432 KB Output is correct
4 Correct 290 ms 57200 KB Output is correct
5 Correct 245 ms 57340 KB Output is correct
6 Correct 347 ms 56812 KB Output is correct
7 Correct 272 ms 61304 KB Output is correct
8 Correct 391 ms 62948 KB Output is correct
9 Correct 553 ms 78320 KB Output is correct
10 Correct 285 ms 69152 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2349 ms 162184 KB Output is correct
2 Correct 2316 ms 173880 KB Output is correct
3 Correct 1018 ms 106596 KB Output is correct
4 Correct 1300 ms 102264 KB Output is correct
5 Correct 1012 ms 103196 KB Output is correct
6 Correct 1782 ms 113128 KB Output is correct
7 Correct 1034 ms 106696 KB Output is correct
8 Correct 1625 ms 142408 KB Output is correct
9 Correct 2584 ms 212192 KB Output is correct
10 Correct 479 ms 113348 KB Output is correct
11 Correct 332 ms 102392 KB Output is correct
12 Correct 321 ms 102264 KB Output is correct
13 Correct 993 ms 105684 KB Output is correct
14 Correct 1172 ms 141100 KB Output is correct