Submission #273761

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-

Submission #273761

Compilation message