oj.uz

Submission #525864

# Submission time Handle Problem Language Result Execution time Memory
525864 2022-02-13T04:10:39 Z koioi.org-koosaga Mountains and Valleys (CCO20_day1problem3) C++17
1 / 25
 1792 ms 38064 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int MAXN = 500005;

struct edge{
	int s, e, x;
};

int n, m;
vector<int> gph[MAXN];
int par[20][MAXN], dep[MAXN];

int lca(int x, int y){
	if(dep[x] > dep[y]) swap(x, y);
	int dx = dep[y] - dep[x];
	for(int i = 0; dx; i++){
		if(dx & 1) y = par[i][y];
		dx >>= 1;
	}
	for(int i = 19; 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;
}

vector<int> ord;
int din[MAXN], dout[MAXN], piv;
int f[20][MAXN], far[MAXN], diam[MAXN], pfar[MAXN];
vector<pi> fars[MAXN];
vector<pi> subDiams[MAXN];

int fPathMax(int x, int v){
	int ans = -1e9;
	for(int i = 0; v; i++){
		if(v & 1){
			ans = max(ans, f[i][x]);
			x = par[i][x];
		}
		v >>= 1;
	}
	return ans;
}

bool in(int u, int v){
	return din[u] <= din[v] && dout[v] <= dout[u];
}

void dfs(int x, int p = -1){
	ord.push_back(x);
	din[x] = ++piv;
	for(auto &y : gph[x]){
		if(y == p) continue;
		par[0][y] = x;
		dep[y] = dep[x] + 1;
		dfs(y, x);
	}
	dout[x] = piv;
}

bool vis[MAXN];

pi dfsl(int x, int p = -1){
	pi ret(0, x);
	for(auto &y : gph[x]){
		if(y == p || vis[y]) continue;
		auto ans = dfsl(y, x);
		ans.first++;
		ret = max(ret, ans);
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	vector<edge> qry;
	for(int i = 0; i < m; i++){
		int s, e, x; cin >> s >> e >> x;
		if(x == 1){
			gph[s].push_back(e);
			gph[e].push_back(s);
		}
		else{
			qry.push_back({s, e, x});
		}
	}
	dfs(0);
	for(int i = 1; i < 20; i++){
		for(int j = 0; j < n; j++){
			par[i][j] = par[i-1][par[i-1][j]];
		}
	}
	{
		for(int i = 0; i < n; i++){
			if(dep[i] >= 2){
				vis[i] = 1;
				vis[par[1][i]] = 1;
				// n^2
				f[0][i] = dfsl(dfsl(par[0][i]).second).first;
				vis[i] = 0;
				vis[par[1][i]] = 0;
			}
		}
		for(int i = 0; i < n; i++){
			vis[i] = 1;
			for(auto &j : gph[i]){
				subDiams[i].emplace_back(dfsl(dfsl(j).second).first, j);
			}
			sort(all(subDiams[i]));
			reverse(all(subDiams[i]));
			vis[i] = 0;
		}
		for(int i = 1; i < 20; i++){
			for(int j = 0; j < n; j++){
				f[i][j] = max(f[i-1][j], f[i-1][par[i-1][j]]);
			}
		}
		reverse(all(ord));
		for(auto &i : ord){
			for(auto &j : gph[i]){
				if(j == par[0][i]) continue;
				far[i] = max(far[i], far[j] + 1);
				diam[i] = max({diam[i], diam[j], far[j] + 1});
				fars[i].emplace_back(far[j], j);
			}
			sort(all(fars[i]));
			reverse(all(fars[i]));
			if(sz(fars[i]) >= 2) diam[i] = max(diam[i], (int)fars[i][0].first + (int)fars[i][1].first + 2);
		}
		reverse(all(ord));
		for(auto &i : ord){
			if(i == 0) continue;
			for(auto &j : fars[par[0][i]]){
				if(j.second == i) continue;
				pfar[i] = j.first + 1;
				break;
			}
			fars[i].emplace_back(pfar[i], par[0][i]);
			sort(all(fars[i]));
			reverse(all(fars[i]));
		}
	}
	int ans = 2 * n - 2 - diam[0];
	for(auto &x : qry){
		int l = lca(x.s, x.e);
		vector<int> v, w;
		for(int i = x.s; i != l; i = par[0][i]) v.push_back(i);
		for(int i = x.e; i != l; i = par[0][i]) w.push_back(i);
		reverse(all(w));
		v.push_back(l);
		for(auto &i : w) v.push_back(i);
		for(auto &i : v) vis[i] = 1;
		vector<int> val;
		int maxPath = -1e9;
		if(dep[x.s] >= dep[l] + 2){
			maxPath = max(maxPath, fPathMax(x.s, dep[x.s] - dep[l] + 1) - 3 + sz(v));
		}
		if(dep[x.e] >= dep[l] + 2){
			maxPath = max(maxPath, fPathMax(x.e, dep[x.e] - dep[l] + 1) - 3 + sz(v));
		}
		if(l != x.s){
			maxPath = max(maxPath, diam[x.s] - 3 + sz(v));
		}
		if(l != x.e){
			maxPath = max(maxPath, diam[x.e] - 3 + sz(v));
		}
		{
			int new_diam = 0;
			int cnt = 0;
			// passes through l
			for(auto &[d, v] : fars[l]){
				if((in(v, x.s) || in(v, x.e)) && v != par[0][l]) continue;
				new_diam += d + 1;
				cnt += 1;
				if(cnt == 2) break;
			}
			for(auto &[d, v] : subDiams[l]){
				if((in(v, x.s) || in(v, x.e)) && v != par[0][l]) continue;
				new_diam = max(new_diam, (int)d);
				break;
			}
			maxPath = max(maxPath, new_diam - 3 + sz(v));
		}
		for(auto &i : v){
			vis[i] = 0;
			val.push_back(dfsl(i).first);
			vis[i] = 1;
		}
		for(auto &i : v) vis[i] = 0;
		int pmax = -1e9;
		for(int i = 0; i < sz(val); i++){
			maxPath = max(maxPath, sz(val) - 1 - i + val[i] + pmax);
			pmax = max(pmax, i + val[i]);
		}
		ans = min(ans, 2 * n - 4 + x.x - maxPath);
	}
	cout << ans << endl;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35788 KB Output is correct
2 Correct 16 ms 35788 KB Output is correct
3 Correct 15 ms 35788 KB Output is correct
4 Correct 16 ms 35988 KB Output is correct
5 Correct 16 ms 35804 KB Output is correct
6 Correct 17 ms 35816 KB Output is correct
7 Correct 18 ms 35816 KB Output is correct
8 Correct 16 ms 35788 KB Output is correct
9 Correct 16 ms 35788 KB Output is correct
10 Correct 16 ms 35788 KB Output is correct
11 Correct 18 ms 35900 KB Output is correct
12 Correct 17 ms 35772 KB Output is correct
13 Correct 17 ms 35820 KB Output is correct
14 Correct 16 ms 35896 KB Output is correct
15 Correct 18 ms 35784 KB Output is correct

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35788 KB Output is correct
2 Correct 16 ms 35788 KB Output is correct
3 Correct 15 ms 35788 KB Output is correct
4 Correct 16 ms 35988 KB Output is correct
5 Correct 16 ms 35804 KB Output is correct
6 Correct 17 ms 35816 KB Output is correct
7 Correct 18 ms 35816 KB Output is correct
8 Correct 16 ms 35788 KB Output is correct
9 Correct 16 ms 35788 KB Output is correct
10 Correct 16 ms 35788 KB Output is correct
11 Correct 18 ms 35900 KB Output is correct
12 Correct 17 ms 35772 KB Output is correct
13 Correct 17 ms 35820 KB Output is correct
14 Correct 16 ms 35896 KB Output is correct
15 Correct 18 ms 35784 KB Output is correct
16 Correct 16 ms 35788 KB Output is correct
17 Correct 16 ms 35788 KB Output is correct
18 Correct 16 ms 35800 KB Output is correct
19 Correct 19 ms 35788 KB Output is correct
20 Correct 17 ms 35788 KB Output is correct
21 Correct 17 ms 35912 KB Output is correct
22 Correct 16 ms 35788 KB Output is correct
23 Correct 18 ms 35780 KB Output is correct
24 Correct 18 ms 35788 KB Output is correct
25 Incorrect 16 ms 35888 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1685 ms 37920 KB Output is correct
2 Correct 1740 ms 37976 KB Output is correct
3 Correct 1668 ms 37972 KB Output is correct
4 Correct 1625 ms 37764 KB Output is correct
5 Correct 1586 ms 37696 KB Output is correct
6 Correct 619 ms 37392 KB Output is correct
7 Correct 1700 ms 38064 KB Output is correct
8 Correct 1792 ms 37832 KB Output is correct
9 Incorrect 1638 ms 37848 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35788 KB Output is correct
2 Correct 16 ms 35788 KB Output is correct
3 Correct 15 ms 35788 KB Output is correct
4 Correct 16 ms 35988 KB Output is correct
5 Correct 16 ms 35804 KB Output is correct
6 Correct 17 ms 35816 KB Output is correct
7 Correct 18 ms 35816 KB Output is correct
8 Correct 16 ms 35788 KB Output is correct
9 Correct 16 ms 35788 KB Output is correct
10 Correct 16 ms 35788 KB Output is correct
11 Correct 18 ms 35900 KB Output is correct
12 Correct 17 ms 35772 KB Output is correct
13 Correct 17 ms 35820 KB Output is correct
14 Correct 16 ms 35896 KB Output is correct
15 Correct 18 ms 35784 KB Output is correct
16 Correct 16 ms 35788 KB Output is correct
17 Correct 16 ms 35788 KB Output is correct
18 Correct 16 ms 35800 KB Output is correct
19 Correct 19 ms 35788 KB Output is correct
20 Correct 17 ms 35788 KB Output is correct
21 Correct 17 ms 35912 KB Output is correct
22 Correct 16 ms 35788 KB Output is correct
23 Correct 18 ms 35780 KB Output is correct
24 Correct 18 ms 35788 KB Output is correct
25 Incorrect 16 ms 35888 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35788 KB Output is correct
2 Correct 16 ms 35788 KB Output is correct
3 Correct 15 ms 35788 KB Output is correct
4 Correct 16 ms 35988 KB Output is correct
5 Correct 16 ms 35804 KB Output is correct
6 Correct 17 ms 35816 KB Output is correct
7 Correct 18 ms 35816 KB Output is correct
8 Correct 16 ms 35788 KB Output is correct
9 Correct 16 ms 35788 KB Output is correct
10 Correct 16 ms 35788 KB Output is correct
11 Correct 18 ms 35900 KB Output is correct
12 Correct 17 ms 35772 KB Output is correct
13 Correct 17 ms 35820 KB Output is correct
14 Correct 16 ms 35896 KB Output is correct
15 Correct 18 ms 35784 KB Output is correct
16 Correct 16 ms 35788 KB Output is correct
17 Correct 16 ms 35788 KB Output is correct
18 Correct 16 ms 35800 KB Output is correct
19 Correct 19 ms 35788 KB Output is correct
20 Correct 17 ms 35788 KB Output is correct
21 Correct 17 ms 35912 KB Output is correct
22 Correct 16 ms 35788 KB Output is correct
23 Correct 18 ms 35780 KB Output is correct
24 Correct 18 ms 35788 KB Output is correct
25 Incorrect 16 ms 35888 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35788 KB Output is correct
2 Correct 16 ms 35788 KB Output is correct
3 Correct 15 ms 35788 KB Output is correct
4 Correct 16 ms 35988 KB Output is correct
5 Correct 16 ms 35804 KB Output is correct
6 Correct 17 ms 35816 KB Output is correct
7 Correct 18 ms 35816 KB Output is correct
8 Correct 16 ms 35788 KB Output is correct
9 Correct 16 ms 35788 KB Output is correct
10 Correct 16 ms 35788 KB Output is correct
11 Correct 18 ms 35900 KB Output is correct
12 Correct 17 ms 35772 KB Output is correct
13 Correct 17 ms 35820 KB Output is correct
14 Correct 16 ms 35896 KB Output is correct
15 Correct 18 ms 35784 KB Output is correct
16 Correct 16 ms 35788 KB Output is correct
17 Correct 16 ms 35788 KB Output is correct
18 Correct 16 ms 35800 KB Output is correct
19 Correct 19 ms 35788 KB Output is correct
20 Correct 17 ms 35788 KB Output is correct
21 Correct 17 ms 35912 KB Output is correct
22 Correct 16 ms 35788 KB Output is correct
23 Correct 18 ms 35780 KB Output is correct
24 Correct 18 ms 35788 KB Output is correct
25 Incorrect 16 ms 35888 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35788 KB Output is correct
2 Correct 16 ms 35788 KB Output is correct
3 Correct 15 ms 35788 KB Output is correct
4 Correct 16 ms 35988 KB Output is correct
5 Correct 16 ms 35804 KB Output is correct
6 Correct 17 ms 35816 KB Output is correct
7 Correct 18 ms 35816 KB Output is correct
8 Correct 16 ms 35788 KB Output is correct
9 Correct 16 ms 35788 KB Output is correct
10 Correct 16 ms 35788 KB Output is correct
11 Correct 18 ms 35900 KB Output is correct
12 Correct 17 ms 35772 KB Output is correct
13 Correct 17 ms 35820 KB Output is correct
14 Correct 16 ms 35896 KB Output is correct
15 Correct 18 ms 35784 KB Output is correct
16 Correct 16 ms 35788 KB Output is correct
17 Correct 16 ms 35788 KB Output is correct
18 Correct 16 ms 35800 KB Output is correct
19 Correct 19 ms 35788 KB Output is correct
20 Correct 17 ms 35788 KB Output is correct
21 Correct 17 ms 35912 KB Output is correct
22 Correct 16 ms 35788 KB Output is correct
23 Correct 18 ms 35780 KB Output is correct
24 Correct 18 ms 35788 KB Output is correct
25 Incorrect 16 ms 35888 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 35788 KB Output is correct
2 Correct 16 ms 35788 KB Output is correct
3 Correct 15 ms 35788 KB Output is correct
4 Correct 16 ms 35988 KB Output is correct
5 Correct 16 ms 35804 KB Output is correct
6 Correct 17 ms 35816 KB Output is correct
7 Correct 18 ms 35816 KB Output is correct
8 Correct 16 ms 35788 KB Output is correct
9 Correct 16 ms 35788 KB Output is correct
10 Correct 16 ms 35788 KB Output is correct
11 Correct 18 ms 35900 KB Output is correct
12 Correct 17 ms 35772 KB Output is correct
13 Correct 17 ms 35820 KB Output is correct
14 Correct 16 ms 35896 KB Output is correct
15 Correct 18 ms 35784 KB Output is correct
16 Correct 16 ms 35788 KB Output is correct
17 Correct 16 ms 35788 KB Output is correct
18 Correct 16 ms 35800 KB Output is correct
19 Correct 19 ms 35788 KB Output is correct
20 Correct 17 ms 35788 KB Output is correct
21 Correct 17 ms 35912 KB Output is correct
22 Correct 16 ms 35788 KB Output is correct
23 Correct 18 ms 35780 KB Output is correct
24 Correct 18 ms 35788 KB Output is correct
25 Incorrect 16 ms 35888 KB Output isn't correct
26 Halted 0 ms 0 KB -