oj.uz

Submission #273758

# Submission time Handle Problem Language Result Execution time Memory
273758 2020-08-19T07:06:48 Z 임성재(#5106) Mountains and Valleys (CCO20_day1problem3) C++17
0 / 25
 7000 ms 25088 KB 
#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 16 ms 23808 KB Output is correct
2 Incorrect 16 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Incorrect 16 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 2.0

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

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Incorrect 16 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Incorrect 16 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Incorrect 16 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Incorrect 16 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Incorrect 16 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -