oj.uz

Submission #274139

# Submission time Handle Problem Language Result Execution time Memory
274139 2020-08-19T08:43:56 Z 임성재(#5106) Mountains and Valleys (CCO20_day1problem3) C++17
0 / 25
 7000 ms 111012 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<pair<pii, int>> e;
vector<int> g[500010];
int dis[5010][5010];
int d[5010];
int sp[5010][21];

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) {
	if(dis[a][b] >= 0) return dis[a][b];

	return dis[a][b] = d[a] + d[b] - 2 * d[lca(a, b)];
}

pii uni(pii x, pii y) {
	pii ret = x;

	if(dist(y.fi, y.se) > dist(ret.fi, ret.se)) ret = y;
	if(dist(x.fi, y.fi) > dist(ret.fi, ret.se)) ret = mp(x.fi, y.fi);
	if(dist(x.fi, y.se) > dist(ret.fi, ret.se)) ret = mp(x.fi, y.se);
	if(dist(x.se, y.fi) > dist(ret.fi, ret.se)) ret = mp(x.se, y.fi);
	if(dist(x.se, y.se) > dist(ret.fi, ret.se)) ret = mp(x.se, y.se);

	return ret;
}

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

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

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

pii f(int r, int x, int y) {
	queue<int> q;
	int dp[5010] = {};

	dp[r] = 1;
	q.em(r);

	while(q.size()) {
		int c = q.front();
		q.pop();

		for(auto i : g[c]) {
			if(dp[i] || i == x || i == y) continue;

			dp[i] = dp[c] + 1;
			q.em(i);
		}
	}

	int mx = -1, mxi=0;
	for(int i=0; i<n; i++) {
		if(dp[i]-1 > mx) {
			mx = dp[i] - 1;
			mxi = i;
		}
	}

	return mp(mx, mxi);
}

pii D(int x, int p, int q) {
	int u = f(x, p, q).se;
	int v = f(u, p, q).se;

	return mp(u, v);
}

int main() {
	fast;

	cin >> n >> m;

	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			dis[i][j] = -1;
	
	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, -1, -1).fi, D(0, -1, -1).se);

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

		for(int i=x; i; i = sp[i][0]) {
			int u, v, l;

			tie(u, v) = D(i, sp[i][0], -1);
			l = max(dist(u, x), dist(v, x));

			tie(u, v) = D(sp[i][0], i, -1);
			l += max(dist(u, y), dist(v, y));

			//ans = min(ans, 2 * n - 4 + w - l);
		}

		for(int i=y; i; i = sp[i][0]) {
			int u, v, l;
			
			tie(u, v) = D(sp[i][0], i, -1);
			l = max(dist(u, x), dist(v, x));
			//cout << u << " " << v << " " << l << endl;

			tie(u, v) = D(i, sp[i][0], -1);
			l += max(dist(u, y), dist(v, y));
			//cout << u << " " << v << " " << l << endl;

			//cout << x << " " << y << " " << 2 * n - 4 + w - l << " " << l << endl;

			//ans = min(ans, 2 * n - 4 + w - l);
		}
	}

	cout << ans;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:141:7: warning: unused variable 'w' [-Wunused-variable]
  141 |   int w = i.se;
      |       ^

Subtask #1
0.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12160 KB Output is correct
2 Correct 10 ms 12160 KB Output is correct
3 Correct 17 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 10 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 11 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 12 ms 12160 KB Output is correct
10 Correct 13 ms 12160 KB Output is correct
11 Incorrect 9 ms 12144 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 10 ms 12160 KB Output is correct
2 Correct 10 ms 12160 KB Output is correct
3 Correct 17 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 10 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 11 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 12 ms 12160 KB Output is correct
10 Correct 13 ms 12160 KB Output is correct
11 Incorrect 9 ms 12144 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0.0 / 2.0

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

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12160 KB Output is correct
2 Correct 10 ms 12160 KB Output is correct
3 Correct 17 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 10 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 11 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 12 ms 12160 KB Output is correct
10 Correct 13 ms 12160 KB Output is correct
11 Incorrect 9 ms 12144 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 10 ms 12160 KB Output is correct
2 Correct 10 ms 12160 KB Output is correct
3 Correct 17 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 10 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 11 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 12 ms 12160 KB Output is correct
10 Correct 13 ms 12160 KB Output is correct
11 Incorrect 9 ms 12144 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 10 ms 12160 KB Output is correct
2 Correct 10 ms 12160 KB Output is correct
3 Correct 17 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 10 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 11 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 12 ms 12160 KB Output is correct
10 Correct 13 ms 12160 KB Output is correct
11 Incorrect 9 ms 12144 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 10 ms 12160 KB Output is correct
2 Correct 10 ms 12160 KB Output is correct
3 Correct 17 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 10 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 11 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 12 ms 12160 KB Output is correct
10 Correct 13 ms 12160 KB Output is correct
11 Incorrect 9 ms 12144 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 10 ms 12160 KB Output is correct
2 Correct 10 ms 12160 KB Output is correct
3 Correct 17 ms 12160 KB Output is correct
4 Correct 10 ms 12160 KB Output is correct
5 Correct 10 ms 12160 KB Output is correct
6 Correct 9 ms 12160 KB Output is correct
7 Correct 11 ms 12160 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 12 ms 12160 KB Output is correct
10 Correct 13 ms 12160 KB Output is correct
11 Incorrect 9 ms 12144 KB Output isn't correct
12 Halted 0 ms 0 KB -