oj.uz

답안 #525861

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525861 2022-02-13T04:04:34 Z koioi.org-koosaga Mountains and Valleys (CCO20_day1problem3) C++17
1 / 25
 696 ms 25960 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];

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 = 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;
		vector<int> ndiam;
		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;
			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;
			}
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 14 ms 24140 KB Output is correct
3 Correct 11 ms 24140 KB Output is correct
4 Correct 11 ms 24048 KB Output is correct
5 Correct 11 ms 24136 KB Output is correct
6 Correct 11 ms 24076 KB Output is correct
7 Correct 12 ms 24140 KB Output is correct
8 Correct 11 ms 24140 KB Output is correct
9 Correct 13 ms 24140 KB Output is correct
10 Correct 11 ms 24036 KB Output is correct
11 Correct 14 ms 24140 KB Output is correct
12 Correct 11 ms 24140 KB Output is correct
13 Correct 12 ms 24140 KB Output is correct
14 Correct 12 ms 24100 KB Output is correct
15 Correct 12 ms 24136 KB Output is correct

Subtask #2
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 14 ms 24140 KB Output is correct
3 Correct 11 ms 24140 KB Output is correct
4 Correct 11 ms 24048 KB Output is correct
5 Correct 11 ms 24136 KB Output is correct
6 Correct 11 ms 24076 KB Output is correct
7 Correct 12 ms 24140 KB Output is correct
8 Correct 11 ms 24140 KB Output is correct
9 Correct 13 ms 24140 KB Output is correct
10 Correct 11 ms 24036 KB Output is correct
11 Correct 14 ms 24140 KB Output is correct
12 Correct 11 ms 24140 KB Output is correct
13 Correct 12 ms 24140 KB Output is correct
14 Correct 12 ms 24100 KB Output is correct
15 Correct 12 ms 24136 KB Output is correct
16 Correct 11 ms 24140 KB Output is correct
17 Correct 11 ms 24140 KB Output is correct
18 Correct 13 ms 24140 KB Output is correct
19 Correct 11 ms 24092 KB Output is correct
20 Correct 11 ms 24068 KB Output is correct
21 Correct 11 ms 24140 KB Output is correct
22 Correct 11 ms 24140 KB Output is correct
23 Correct 12 ms 24100 KB Output is correct
24 Correct 11 ms 24148 KB Output is correct
25 Incorrect 12 ms 24136 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 606 ms 25860 KB Output is correct
2 Correct 554 ms 25960 KB Output is correct
3 Correct 561 ms 25768 KB Output is correct
4 Correct 541 ms 25744 KB Output is correct
5 Correct 578 ms 25684 KB Output is correct
6 Correct 376 ms 25628 KB Output is correct
7 Correct 583 ms 25932 KB Output is correct
8 Correct 696 ms 25792 KB Output is correct
9 Incorrect 618 ms 25924 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 14 ms 24140 KB Output is correct
3 Correct 11 ms 24140 KB Output is correct
4 Correct 11 ms 24048 KB Output is correct
5 Correct 11 ms 24136 KB Output is correct
6 Correct 11 ms 24076 KB Output is correct
7 Correct 12 ms 24140 KB Output is correct
8 Correct 11 ms 24140 KB Output is correct
9 Correct 13 ms 24140 KB Output is correct
10 Correct 11 ms 24036 KB Output is correct
11 Correct 14 ms 24140 KB Output is correct
12 Correct 11 ms 24140 KB Output is correct
13 Correct 12 ms 24140 KB Output is correct
14 Correct 12 ms 24100 KB Output is correct
15 Correct 12 ms 24136 KB Output is correct
16 Correct 11 ms 24140 KB Output is correct
17 Correct 11 ms 24140 KB Output is correct
18 Correct 13 ms 24140 KB Output is correct
19 Correct 11 ms 24092 KB Output is correct
20 Correct 11 ms 24068 KB Output is correct
21 Correct 11 ms 24140 KB Output is correct
22 Correct 11 ms 24140 KB Output is correct
23 Correct 12 ms 24100 KB Output is correct
24 Correct 11 ms 24148 KB Output is correct
25 Incorrect 12 ms 24136 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 14 ms 24140 KB Output is correct
3 Correct 11 ms 24140 KB Output is correct
4 Correct 11 ms 24048 KB Output is correct
5 Correct 11 ms 24136 KB Output is correct
6 Correct 11 ms 24076 KB Output is correct
7 Correct 12 ms 24140 KB Output is correct
8 Correct 11 ms 24140 KB Output is correct
9 Correct 13 ms 24140 KB Output is correct
10 Correct 11 ms 24036 KB Output is correct
11 Correct 14 ms 24140 KB Output is correct
12 Correct 11 ms 24140 KB Output is correct
13 Correct 12 ms 24140 KB Output is correct
14 Correct 12 ms 24100 KB Output is correct
15 Correct 12 ms 24136 KB Output is correct
16 Correct 11 ms 24140 KB Output is correct
17 Correct 11 ms 24140 KB Output is correct
18 Correct 13 ms 24140 KB Output is correct
19 Correct 11 ms 24092 KB Output is correct
20 Correct 11 ms 24068 KB Output is correct
21 Correct 11 ms 24140 KB Output is correct
22 Correct 11 ms 24140 KB Output is correct
23 Correct 12 ms 24100 KB Output is correct
24 Correct 11 ms 24148 KB Output is correct
25 Incorrect 12 ms 24136 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 14 ms 24140 KB Output is correct
3 Correct 11 ms 24140 KB Output is correct
4 Correct 11 ms 24048 KB Output is correct
5 Correct 11 ms 24136 KB Output is correct
6 Correct 11 ms 24076 KB Output is correct
7 Correct 12 ms 24140 KB Output is correct
8 Correct 11 ms 24140 KB Output is correct
9 Correct 13 ms 24140 KB Output is correct
10 Correct 11 ms 24036 KB Output is correct
11 Correct 14 ms 24140 KB Output is correct
12 Correct 11 ms 24140 KB Output is correct
13 Correct 12 ms 24140 KB Output is correct
14 Correct 12 ms 24100 KB Output is correct
15 Correct 12 ms 24136 KB Output is correct
16 Correct 11 ms 24140 KB Output is correct
17 Correct 11 ms 24140 KB Output is correct
18 Correct 13 ms 24140 KB Output is correct
19 Correct 11 ms 24092 KB Output is correct
20 Correct 11 ms 24068 KB Output is correct
21 Correct 11 ms 24140 KB Output is correct
22 Correct 11 ms 24140 KB Output is correct
23 Correct 12 ms 24100 KB Output is correct
24 Correct 11 ms 24148 KB Output is correct
25 Incorrect 12 ms 24136 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 14 ms 24140 KB Output is correct
3 Correct 11 ms 24140 KB Output is correct
4 Correct 11 ms 24048 KB Output is correct
5 Correct 11 ms 24136 KB Output is correct
6 Correct 11 ms 24076 KB Output is correct
7 Correct 12 ms 24140 KB Output is correct
8 Correct 11 ms 24140 KB Output is correct
9 Correct 13 ms 24140 KB Output is correct
10 Correct 11 ms 24036 KB Output is correct
11 Correct 14 ms 24140 KB Output is correct
12 Correct 11 ms 24140 KB Output is correct
13 Correct 12 ms 24140 KB Output is correct
14 Correct 12 ms 24100 KB Output is correct
15 Correct 12 ms 24136 KB Output is correct
16 Correct 11 ms 24140 KB Output is correct
17 Correct 11 ms 24140 KB Output is correct
18 Correct 13 ms 24140 KB Output is correct
19 Correct 11 ms 24092 KB Output is correct
20 Correct 11 ms 24068 KB Output is correct
21 Correct 11 ms 24140 KB Output is correct
22 Correct 11 ms 24140 KB Output is correct
23 Correct 12 ms 24100 KB Output is correct
24 Correct 11 ms 24148 KB Output is correct
25 Incorrect 12 ms 24136 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 24140 KB Output is correct
2 Correct 14 ms 24140 KB Output is correct
3 Correct 11 ms 24140 KB Output is correct
4 Correct 11 ms 24048 KB Output is correct
5 Correct 11 ms 24136 KB Output is correct
6 Correct 11 ms 24076 KB Output is correct
7 Correct 12 ms 24140 KB Output is correct
8 Correct 11 ms 24140 KB Output is correct
9 Correct 13 ms 24140 KB Output is correct
10 Correct 11 ms 24036 KB Output is correct
11 Correct 14 ms 24140 KB Output is correct
12 Correct 11 ms 24140 KB Output is correct
13 Correct 12 ms 24140 KB Output is correct
14 Correct 12 ms 24100 KB Output is correct
15 Correct 12 ms 24136 KB Output is correct
16 Correct 11 ms 24140 KB Output is correct
17 Correct 11 ms 24140 KB Output is correct
18 Correct 13 ms 24140 KB Output is correct
19 Correct 11 ms 24092 KB Output is correct
20 Correct 11 ms 24068 KB Output is correct
21 Correct 11 ms 24140 KB Output is correct
22 Correct 11 ms 24140 KB Output is correct
23 Correct 12 ms 24100 KB Output is correct
24 Correct 11 ms 24148 KB Output is correct
25 Incorrect 12 ms 24136 KB Output isn't correct
26 Halted 0 ms 0 KB -