oj.uz

Submission #291910

# Submission time Handle Problem Language Result Execution time Memory
291910 2020-09-06T01:53:53 Z Diuven ROI16_sending (ROI16_sending) C++11
100 / 100
 4178 ms 194328 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 = 18;
const int N = (int) 2e5 + 10;
int n, m, curt, u, v, opt = 0, opti = 0, optj = 1, h[N], intime[N], outime[N], p[N][L];
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(intime[a.fs], a.sc) < mp(intime[b.fs], b.sc));
	}
};

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

void dfs(int v, int pv = -1) {
	intime[v] = curt++;
	for (int u : adj[v]) {
		if (u != pv) {
			p[u][0] = v;
			h[u] += h[v];
			dfs(u, v);
		}
	}
	outime[v] = curt++;
}

bool is_parent(int u, int v) {
	return (intime[u] <= intime[v]) && (outime[v] <= outime[u]);
}

int lca(int u, int v) {
	if (is_parent(u, v)) {
		return u;
	}
	for (int j = L - 1; j >= 0; --j) {
		if (!is_parent(p[u][j], v)) {
			u = p[u][j];
		}
	}
	return p[u][0];
}

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);
	for (int j = 1; j < L; ++j)
		for (int i = 0; i < n; ++i)
			p[i][j] = p[p[i][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:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
sending.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |   scanf("%d", &u), --u;
      |   ~~~~~^~~~~~~~~~
sending.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |   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 15 ms 23808 KB Output is correct
4 Correct 16 ms 23808 KB Output is correct
5 Correct 17 ms 23808 KB Output is correct
6 Correct 19 ms 23808 KB Output is correct
7 Correct 17 ms 23808 KB Output is correct
8 Correct 16 ms 23808 KB Output is correct
9 Correct 19 ms 23808 KB Output is correct
10 Correct 16 ms 23808 KB Output is correct
11 Correct 16 ms 23808 KB Output is correct
12 Correct 19 ms 23760 KB Output is correct
13 Correct 17 ms 23888 KB Output is correct
14 Correct 23 ms 23808 KB Output is correct
15 Correct 15 ms 23808 KB Output is correct
16 Correct 14 ms 23808 KB Output is correct
17 Correct 16 ms 23808 KB Output is correct
18 Correct 16 ms 23808 KB Output is correct
19 Correct 16 ms 23808 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24576 KB Output is correct
2 Correct 27 ms 24576 KB Output is correct
3 Correct 20 ms 24908 KB Output is correct
4 Correct 22 ms 24672 KB Output is correct
5 Correct 20 ms 24704 KB Output is correct
6 Correct 21 ms 24576 KB Output is correct
7 Correct 20 ms 24832 KB Output is correct
8 Correct 23 ms 24560 KB Output is correct
9 Correct 28 ms 24704 KB Output is correct
10 Correct 19 ms 24832 KB Output is correct
11 Correct 17 ms 24832 KB Output is correct
12 Correct 17 ms 24832 KB Output is correct
13 Correct 22 ms 24832 KB Output is correct
14 Correct 24 ms 24732 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 35700 KB Output is correct
2 Correct 120 ms 35632 KB Output is correct
3 Correct 95 ms 47816 KB Output is correct
4 Correct 78 ms 41592 KB Output is correct
5 Correct 74 ms 41568 KB Output is correct
6 Correct 58 ms 35824 KB Output is correct
7 Correct 89 ms 47856 KB Output is correct
8 Correct 67 ms 36088 KB Output is correct
9 Correct 79 ms 35704 KB Output is correct
10 Correct 89 ms 46512 KB Output is correct
11 Correct 75 ms 46456 KB Output is correct
12 Correct 82 ms 46536 KB Output is correct
13 Correct 96 ms 46588 KB Output is correct
14 Correct 84 ms 36984 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 37480 KB Output is correct
2 Correct 174 ms 37752 KB Output is correct
3 Correct 106 ms 48248 KB Output is correct
4 Correct 101 ms 42196 KB Output is correct
5 Correct 101 ms 42232 KB Output is correct
6 Correct 72 ms 36848 KB Output is correct
7 Correct 142 ms 48252 KB Output is correct
8 Correct 87 ms 37624 KB Output is correct
9 Correct 133 ms 38264 KB Output is correct
10 Correct 93 ms 47096 KB Output is correct
11 Correct 90 ms 46840 KB Output is correct
12 Correct 101 ms 46700 KB Output is correct
13 Correct 115 ms 46968 KB Output is correct
14 Correct 97 ms 46588 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 59744 KB Output is correct
2 Correct 799 ms 58520 KB Output is correct
3 Correct 756 ms 59828 KB Output is correct
4 Correct 813 ms 58132 KB Output is correct
5 Correct 643 ms 58724 KB Output is correct
6 Correct 758 ms 58588 KB Output is correct
7 Correct 801 ms 59872 KB Output is correct
8 Correct 802 ms 58136 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 43896 KB Output is correct
2 Correct 400 ms 44860 KB Output is correct
3 Correct 371 ms 52020 KB Output is correct
4 Correct 344 ms 45304 KB Output is correct
5 Correct 383 ms 46712 KB Output is correct
6 Correct 255 ms 45032 KB Output is correct
7 Correct 388 ms 51960 KB Output is correct
8 Correct 245 ms 45300 KB Output is correct
9 Correct 366 ms 46104 KB Output is correct
10 Correct 171 ms 53976 KB Output is correct
11 Correct 126 ms 51192 KB Output is correct
12 Correct 115 ms 51236 KB Output is correct
13 Correct 393 ms 52400 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 799 ms 58476 KB Output is correct
2 Correct 904 ms 61292 KB Output is correct
3 Correct 382 ms 52344 KB Output is correct
4 Correct 403 ms 48240 KB Output is correct
5 Correct 447 ms 48376 KB Output is correct
6 Correct 348 ms 47988 KB Output is correct
7 Correct 348 ms 52344 KB Output is correct
8 Correct 548 ms 54120 KB Output is correct
9 Correct 1002 ms 69388 KB Output is correct
10 Correct 352 ms 60140 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3500 ms 144140 KB Output is correct
2 Correct 4178 ms 155940 KB Output is correct
3 Correct 1712 ms 88696 KB Output is correct
4 Correct 1914 ms 84324 KB Output is correct
5 Correct 1998 ms 85320 KB Output is correct
6 Correct 1739 ms 95172 KB Output is correct
7 Correct 1523 ms 88696 KB Output is correct
8 Correct 2160 ms 124608 KB Output is correct
9 Correct 4153 ms 194328 KB Output is correct
10 Correct 471 ms 95300 KB Output is correct
11 Correct 353 ms 84344 KB Output is correct
12 Correct 382 ms 84472 KB Output is correct
13 Correct 1736 ms 87940 KB Output is correct
14 Correct 1568 ms 122992 KB Output is correct