답안 #273761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
273761	2020-08-19T07:08:09 Z	임성재(#5106)	Mountains and Valleys (CCO20_day1problem3)	C++17	2 / 25	30 ms	25216 KB

Main

#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
vector<int> g[500010];
int d[500010];
int sp[500010][21];
vector<int> D[500010];
vector<pair<pii, int>> e;

int lca(int a, int b) {
	if(d[a] > d[b]) swap(a, b);

	for(int i=20; i>=0; i--) {
		if(d[b] - d[a] >= (1<<i)) b = sp[b][i];
	}

	if(a == b) return a;

	for(int i=20; i>=0; i--) {
		if(sp[a][i] != sp[b][i]) {
			a = sp[a][i];
			b = sp[b][i];
		}
	}

	return sp[a][0];
}

int dist(int a, int b) {
	return d[a] + d[b] - 2 * d[lca(a, b)];
}

void dfs(int x) {
	for(int i=1; i<=20; i++)
		sp[x][i] = sp[sp[x][i-1]][i-1];

	D[x].eb(x);
	D[x].eb(x);

	for(auto i : g[x]) {
		if(i == sp[x][0]) continue;

		d[i] = d[x] + 1;
		sp[i][0] = x;
		dfs(i);

		int mx = dist(D[x][0], D[x][1]);
		pii mxi = mp(D[x][0], D[x][1]);

		if(dist(D[i][0], D[i][1]) > mx) {
			mx = dist(D[i][0], D[i][1]);
			mxi = mp(D[i][0], D[i][1]);
		}

		for(int j=0; j<2; j++) {
			for(int k=0; k<2; k++) {
				if(dist(D[x][j], D[i][k]) > mx) {
					mx = dist(D[x][j], D[i][k]);
					mxi = mp(D[x][j], D[i][k]);
				}
			}
		}

		D[x][0] = mxi.fi;
		D[x][1] = mxi.se;
	}
}

int main() {
	fast;

	cin >> n >> m;

	for(int i=0; i<m; i++) {
		int x, y, w;
		cin >> x >> y >> w;

		if(w == 1) {
			g[x].eb(y);
			g[y].eb(x);
		}
		else {
			e.eb(mp(x, y), w);
		}
	}

	dfs(0);

	int ans = 2 * n - 2 - dist(D[0][0], D[0][1]);

	/*for(auto i : e) {
		int x = i.fi.fi;
		int y = i.fi.se;
		int w = i.se;

		for(int u=0; u<n; u++) {
			for(int v = 0; v<n; v++) {
				int f = 2 * n - 2 + w;
				f -= dist(x, u) + dist(y, v);
				
				if(d[lca(x, u)] > d[lca(x, y)] || d[lca(y, v)] > d[lca(x, y)]) f -= 2;
				else {
					f += 2 * (d[lca(x, y)] - max(d[lca(x, u)], d[lca(y, v)]));
				}

				ans = min(ans, f);
			}
		}
	}*/

	cout << ans;
}

Subtask #1
0.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23808 KB	Output is correct
2	Correct	19 ms	23808 KB	Output is correct
3	Correct	19 ms	23808 KB	Output is correct
4	Correct	17 ms	23808 KB	Output is correct
5	Correct	16 ms	23808 KB	Output is correct
6	Correct	16 ms	23808 KB	Output is correct
7	Correct	19 ms	23808 KB	Output is correct
8	Correct	16 ms	23808 KB	Output is correct
9	Correct	16 ms	23808 KB	Output is correct
10	Correct	16 ms	23808 KB	Output is correct
11	Incorrect	19 ms	23808 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #2
0.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23808 KB	Output is correct
2	Correct	19 ms	23808 KB	Output is correct
3	Correct	19 ms	23808 KB	Output is correct
4	Correct	17 ms	23808 KB	Output is correct
5	Correct	16 ms	23808 KB	Output is correct
6	Correct	16 ms	23808 KB	Output is correct
7	Correct	19 ms	23808 KB	Output is correct
8	Correct	16 ms	23808 KB	Output is correct
9	Correct	16 ms	23808 KB	Output is correct
10	Correct	16 ms	23808 KB	Output is correct
11	Incorrect	19 ms	23808 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #3
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	25088 KB	Output is correct
2	Correct	24 ms	25216 KB	Output is correct
3	Correct	27 ms	24956 KB	Output is correct
4	Correct	24 ms	24832 KB	Output is correct
5	Correct	24 ms	24832 KB	Output is correct
6	Correct	24 ms	24608 KB	Output is correct
7	Correct	27 ms	25088 KB	Output is correct
8	Correct	29 ms	25084 KB	Output is correct
9	Correct	26 ms	25088 KB	Output is correct
10	Correct	24 ms	24880 KB	Output is correct
11	Correct	24 ms	24960 KB	Output is correct
12	Correct	23 ms	24832 KB	Output is correct
13	Correct	23 ms	24832 KB	Output is correct
14	Correct	24 ms	24960 KB	Output is correct

Subtask #4
0.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23808 KB	Output is correct
2	Correct	19 ms	23808 KB	Output is correct
3	Correct	19 ms	23808 KB	Output is correct
4	Correct	17 ms	23808 KB	Output is correct
5	Correct	16 ms	23808 KB	Output is correct
6	Correct	16 ms	23808 KB	Output is correct
7	Correct	19 ms	23808 KB	Output is correct
8	Correct	16 ms	23808 KB	Output is correct
9	Correct	16 ms	23808 KB	Output is correct
10	Correct	16 ms	23808 KB	Output is correct
11	Incorrect	19 ms	23808 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23808 KB	Output is correct
2	Correct	19 ms	23808 KB	Output is correct
3	Correct	19 ms	23808 KB	Output is correct
4	Correct	17 ms	23808 KB	Output is correct
5	Correct	16 ms	23808 KB	Output is correct
6	Correct	16 ms	23808 KB	Output is correct
7	Correct	19 ms	23808 KB	Output is correct
8	Correct	16 ms	23808 KB	Output is correct
9	Correct	16 ms	23808 KB	Output is correct
10	Correct	16 ms	23808 KB	Output is correct
11	Incorrect	19 ms	23808 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23808 KB	Output is correct
2	Correct	19 ms	23808 KB	Output is correct
3	Correct	19 ms	23808 KB	Output is correct
4	Correct	17 ms	23808 KB	Output is correct
5	Correct	16 ms	23808 KB	Output is correct
6	Correct	16 ms	23808 KB	Output is correct
7	Correct	19 ms	23808 KB	Output is correct
8	Correct	16 ms	23808 KB	Output is correct
9	Correct	16 ms	23808 KB	Output is correct
10	Correct	16 ms	23808 KB	Output is correct
11	Incorrect	19 ms	23808 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23808 KB	Output is correct
2	Correct	19 ms	23808 KB	Output is correct
3	Correct	19 ms	23808 KB	Output is correct
4	Correct	17 ms	23808 KB	Output is correct
5	Correct	16 ms	23808 KB	Output is correct
6	Correct	16 ms	23808 KB	Output is correct
7	Correct	19 ms	23808 KB	Output is correct
8	Correct	16 ms	23808 KB	Output is correct
9	Correct	16 ms	23808 KB	Output is correct
10	Correct	16 ms	23808 KB	Output is correct
11	Incorrect	19 ms	23808 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	23808 KB	Output is correct
2	Correct	19 ms	23808 KB	Output is correct
3	Correct	19 ms	23808 KB	Output is correct
4	Correct	17 ms	23808 KB	Output is correct
5	Correct	16 ms	23808 KB	Output is correct
6	Correct	16 ms	23808 KB	Output is correct
7	Correct	19 ms	23808 KB	Output is correct
8	Correct	16 ms	23808 KB	Output is correct
9	Correct	16 ms	23808 KB	Output is correct
10	Correct	16 ms	23808 KB	Output is correct
11	Incorrect	19 ms	23808 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

답안 #273761

Compilation message