답안 #525733

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525733 2022-02-12T16:38:58 Z koioi.org-koosaga Mountains and Valleys (CCO20_day1problem3) C++17
2 / 25
13 ms 13180 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){
		break;
		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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 6 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 6 ms 12108 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12204 KB Output is correct
8 Correct 9 ms 12212 KB Output is correct
9 Correct 7 ms 12108 KB Output is correct
10 Correct 9 ms 12108 KB Output is correct
11 Incorrect 6 ms 12164 KB Output isn't correct
12 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 6 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 6 ms 12108 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12204 KB Output is correct
8 Correct 9 ms 12212 KB Output is correct
9 Correct 7 ms 12108 KB Output is correct
10 Correct 9 ms 12108 KB Output is correct
11 Incorrect 6 ms 12164 KB Output isn't correct
12 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 13132 KB Output is correct
2 Correct 10 ms 13172 KB Output is correct
3 Correct 11 ms 13068 KB Output is correct
4 Correct 9 ms 12936 KB Output is correct
5 Correct 10 ms 12916 KB Output is correct
6 Correct 10 ms 12892 KB Output is correct
7 Correct 13 ms 13180 KB Output is correct
8 Correct 10 ms 13004 KB Output is correct
9 Correct 10 ms 13136 KB Output is correct
10 Correct 9 ms 13016 KB Output is correct
11 Correct 10 ms 13004 KB Output is correct
12 Correct 10 ms 13008 KB Output is correct
13 Correct 10 ms 13004 KB Output is correct
14 Correct 11 ms 13004 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 6 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 6 ms 12108 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12204 KB Output is correct
8 Correct 9 ms 12212 KB Output is correct
9 Correct 7 ms 12108 KB Output is correct
10 Correct 9 ms 12108 KB Output is correct
11 Incorrect 6 ms 12164 KB Output isn't correct
12 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 6 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 6 ms 12108 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12204 KB Output is correct
8 Correct 9 ms 12212 KB Output is correct
9 Correct 7 ms 12108 KB Output is correct
10 Correct 9 ms 12108 KB Output is correct
11 Incorrect 6 ms 12164 KB Output isn't correct
12 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 6 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 6 ms 12108 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12204 KB Output is correct
8 Correct 9 ms 12212 KB Output is correct
9 Correct 7 ms 12108 KB Output is correct
10 Correct 9 ms 12108 KB Output is correct
11 Incorrect 6 ms 12164 KB Output isn't correct
12 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 6 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 6 ms 12108 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12204 KB Output is correct
8 Correct 9 ms 12212 KB Output is correct
9 Correct 7 ms 12108 KB Output is correct
10 Correct 9 ms 12108 KB Output is correct
11 Incorrect 6 ms 12164 KB Output isn't correct
12 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 6 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 6 ms 12108 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12204 KB Output is correct
8 Correct 9 ms 12212 KB Output is correct
9 Correct 7 ms 12108 KB Output is correct
10 Correct 9 ms 12108 KB Output is correct
11 Incorrect 6 ms 12164 KB Output isn't correct
12 Halted 0 ms 0 KB -