oj.uz

Submission #292714

# Submission time Handle Problem Language Result Execution time Memory
292714 2020-09-07T12:13:20 Z moven(#5823) ROI16_sending (ROI16_sending) C++17
12 / 100
 5000 ms 22784 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 200005;

int n, m;
vector<int> gph[MAXN];
pi a[MAXN];

int par[18][MAXN];
int din[MAXN], dout[MAXN], dep[MAXN], piv;

int anc(int x, int v){
	for(int i=0; v; i++){
		if(v & 1) x = par[i][x];
		v >>= 1;
	}
	return x;
}

int lca(int x, int y){
	if(dep[x] > dep[y]) swap(x, y);
	y = anc(y, dep[y] - dep[x]);
	for(int i=17; i>=0; i--){
		if(par[i][x] != par[i][y]){
			x = par[i][x];
			y = par[i][y];
		}
	}
	if(x != y) return par[0][x];
	return x;
}

struct bar{
	int dist, x, y;
	bool operator<(const bar &t)const{
		return dist < t.dist;
	}
};

struct kek{
	int pp, qq, x, y, idx;
	bool operator<(const kek &k)const{
		return pi(pp, qq) < pi(k.pp, k.qq);
	}
};

bar solve(vector<kek> a, int v){
	bar ret = (bar){-1, -1, -1};
	for(int i=0; i<sz(a); i++){
		for(int j=0; j<i; j++){
			bar w = {dep[lca(a[i].x, a[j].x)] + dep[lca(a[i].y, a[j].y)] - 2 * dep[v], a[i].idx, a[j].idx};
			ret = max(ret, w);
		}
	}
	return ret;
}

void dfs(int x){
	din[x] = piv++;
	for(auto &i : gph[x]){
		dep[i] = dep[x] + 1;
		par[0][i] = x;
		dfs(i);
	}
	dout[x] = piv;
}

pi up[MAXN][2];

void upload(int x, pi v){
	if(up[x][0] > v){
		up[x][1] = up[x][0];
		up[x][0] = v;
	}
	else if(up[x][1] > v){
		up[x][1] = v;
	}
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=2; i<=n; i++){
		int x; scanf("%d",&x);
		gph[x].push_back(i);
	}
	dfs(1);
	for(int i=1; i<18; i++){
		for(int j=1; j<=n; j++){
			par[i][j] = par[i-1][par[i-1][j]];
		}
	}
	for(int i=1; i<=n; i++) up[i][0] = up[i][1] = pi(1e9, 0);
	vector<kek> v;
	for(int i=1; i<=m; i++){
		int x, y; scanf("%d %d",&x,&y);
		int l = lca(x, y);
		if(l != x) upload(x, pi(dep[l], i));
		if(l != y) upload(y, pi(dep[l], i));
		if(l != x && l != y){
			int cx = anc(x, dep[x] - dep[l] - 1);
			int cy = anc(y, dep[y] - dep[l] - 1);
			if(cx > cy) swap(cx, cy);
			v.push_back({cx, cy, x, y, i});
		}
	}
	sort(all(v));
	bar ans = {0, 1, 2};
	for(int i=n; i; i--){
		for(auto &j : gph[i]){
			upload(i, up[j][0]);
			upload(i, up[j][1]);
		}
		if(up[i][1].second){
			int dist = dep[i] - up[i][1].first;
			if(dist > 0) ans = max(ans, (bar){dist, up[i][0].second, up[i][1].second});
		}
	}
	for(int i=0; i<sz(v); ){
		int e = i;
		while(e < sz(v) && pi(v[e].pp, v[e].qq) == pi(v[i].pp, v[i].qq)) e++;
		vector<kek> w;
		for(int j=i; j<e; j++) w.push_back(v[j]);
		ans = max(ans, solve(w, par[0][v[i].pp]));
		i = e;
	}
	printf("%d\n%d %d\n", ans.dist, ans.x, ans.y);
}

Compilation message

sending.cpp: In function 'int main()':
sending.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
sending.cpp:87:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |   int x; scanf("%d",&x);
      |          ~~~~~^~~~~~~~~
sending.cpp:99:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |   int x, y; scanf("%d %d",&x,&y);
      |             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Incorrect 4 ms 5120 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Incorrect 4 ms 5120 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Incorrect 4 ms 5120 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Incorrect 4 ms 5120 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5074 ms 17904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 16504 KB Output is correct
2 Correct 99 ms 16792 KB Output is correct
3 Correct 137 ms 22648 KB Output is correct
4 Correct 131 ms 20352 KB Output is correct
5 Correct 131 ms 18816 KB Output is correct
6 Correct 44 ms 15480 KB Output is correct
7 Correct 135 ms 22776 KB Output is correct
8 Correct 52 ms 15480 KB Output is correct
9 Correct 72 ms 16512 KB Output is correct
10 Correct 56 ms 22776 KB Output is correct
11 Correct 50 ms 22776 KB Output is correct
12 Correct 47 ms 22784 KB Output is correct
13 Correct 147 ms 22776 KB Output is correct

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Incorrect 4 ms 5120 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5120 KB Output is correct
2 Correct 4 ms 5120 KB Output is correct
3 Correct 4 ms 5120 KB Output is correct
4 Correct 4 ms 5120 KB Output is correct
5 Correct 4 ms 5120 KB Output is correct
6 Incorrect 4 ms 5120 KB Output isn't correct
7 Halted 0 ms 0 KB -