oj.uz

Submission #525732

# Submission time Handle Problem Language Result Execution time Memory
525732 2022-02-12T16:33:15 Z koioi.org-koosaga Mountains and Valleys (CCO20_day1problem3) C++17
1 / 25
 7000 ms 13220 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;
}

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

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]];
		}
	}
	int ans = 2 * n - 2 - dfsl(dfsl(0).second).first;
	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;
		for(auto &i : v){
			val.push_back(dfsl(i).first);
		}
		for(auto &i : v) vis[i] = 0;
		int maxPath = 0;
		for(int i = 0; i < sz(val); i++){
			for(int j = i + 1; j < sz(val); j++){
				maxPath = max(maxPath, sz(val) - 1 - j + i + val[i] + val[j] + x.x);
			}
		}
		ans = min(ans, 2 * n - 4 + 2 * x.x - maxPath);
	}
	cout << ans << endl;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12108 KB Output is correct
2 Correct 7 ms 12108 KB Output is correct
3 Correct 6 ms 12108 KB Output is correct
4 Correct 7 ms 12180 KB Output is correct
5 Correct 7 ms 12160 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12108 KB Output is correct
8 Correct 6 ms 12108 KB Output is correct
9 Correct 6 ms 12108 KB Output is correct
10 Correct 7 ms 12104 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 6 ms 12108 KB Output is correct
13 Correct 6 ms 12108 KB Output is correct
14 Correct 6 ms 12108 KB Output is correct
15 Correct 6 ms 12108 KB Output is correct

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12108 KB Output is correct
2 Correct 7 ms 12108 KB Output is correct
3 Correct 6 ms 12108 KB Output is correct
4 Correct 7 ms 12180 KB Output is correct
5 Correct 7 ms 12160 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12108 KB Output is correct
8 Correct 6 ms 12108 KB Output is correct
9 Correct 6 ms 12108 KB Output is correct
10 Correct 7 ms 12104 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 6 ms 12108 KB Output is correct
13 Correct 6 ms 12108 KB Output is correct
14 Correct 6 ms 12108 KB Output is correct
15 Correct 6 ms 12108 KB Output is correct
16 Correct 6 ms 12148 KB Output is correct
17 Correct 6 ms 12108 KB Output is correct
18 Incorrect 6 ms 12108 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0.0 / 2.0

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

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12108 KB Output is correct
2 Correct 7 ms 12108 KB Output is correct
3 Correct 6 ms 12108 KB Output is correct
4 Correct 7 ms 12180 KB Output is correct
5 Correct 7 ms 12160 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12108 KB Output is correct
8 Correct 6 ms 12108 KB Output is correct
9 Correct 6 ms 12108 KB Output is correct
10 Correct 7 ms 12104 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 6 ms 12108 KB Output is correct
13 Correct 6 ms 12108 KB Output is correct
14 Correct 6 ms 12108 KB Output is correct
15 Correct 6 ms 12108 KB Output is correct
16 Correct 6 ms 12148 KB Output is correct
17 Correct 6 ms 12108 KB Output is correct
18 Incorrect 6 ms 12108 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12108 KB Output is correct
2 Correct 7 ms 12108 KB Output is correct
3 Correct 6 ms 12108 KB Output is correct
4 Correct 7 ms 12180 KB Output is correct
5 Correct 7 ms 12160 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12108 KB Output is correct
8 Correct 6 ms 12108 KB Output is correct
9 Correct 6 ms 12108 KB Output is correct
10 Correct 7 ms 12104 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 6 ms 12108 KB Output is correct
13 Correct 6 ms 12108 KB Output is correct
14 Correct 6 ms 12108 KB Output is correct
15 Correct 6 ms 12108 KB Output is correct
16 Correct 6 ms 12148 KB Output is correct
17 Correct 6 ms 12108 KB Output is correct
18 Incorrect 6 ms 12108 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12108 KB Output is correct
2 Correct 7 ms 12108 KB Output is correct
3 Correct 6 ms 12108 KB Output is correct
4 Correct 7 ms 12180 KB Output is correct
5 Correct 7 ms 12160 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12108 KB Output is correct
8 Correct 6 ms 12108 KB Output is correct
9 Correct 6 ms 12108 KB Output is correct
10 Correct 7 ms 12104 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 6 ms 12108 KB Output is correct
13 Correct 6 ms 12108 KB Output is correct
14 Correct 6 ms 12108 KB Output is correct
15 Correct 6 ms 12108 KB Output is correct
16 Correct 6 ms 12148 KB Output is correct
17 Correct 6 ms 12108 KB Output is correct
18 Incorrect 6 ms 12108 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12108 KB Output is correct
2 Correct 7 ms 12108 KB Output is correct
3 Correct 6 ms 12108 KB Output is correct
4 Correct 7 ms 12180 KB Output is correct
5 Correct 7 ms 12160 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12108 KB Output is correct
8 Correct 6 ms 12108 KB Output is correct
9 Correct 6 ms 12108 KB Output is correct
10 Correct 7 ms 12104 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 6 ms 12108 KB Output is correct
13 Correct 6 ms 12108 KB Output is correct
14 Correct 6 ms 12108 KB Output is correct
15 Correct 6 ms 12108 KB Output is correct
16 Correct 6 ms 12148 KB Output is correct
17 Correct 6 ms 12108 KB Output is correct
18 Incorrect 6 ms 12108 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12108 KB Output is correct
2 Correct 7 ms 12108 KB Output is correct
3 Correct 6 ms 12108 KB Output is correct
4 Correct 7 ms 12180 KB Output is correct
5 Correct 7 ms 12160 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12108 KB Output is correct
8 Correct 6 ms 12108 KB Output is correct
9 Correct 6 ms 12108 KB Output is correct
10 Correct 7 ms 12104 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 6 ms 12108 KB Output is correct
13 Correct 6 ms 12108 KB Output is correct
14 Correct 6 ms 12108 KB Output is correct
15 Correct 6 ms 12108 KB Output is correct
16 Correct 6 ms 12148 KB Output is correct
17 Correct 6 ms 12108 KB Output is correct
18 Incorrect 6 ms 12108 KB Output isn't correct
19 Halted 0 ms 0 KB -