oj.uz

답안 #274144

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
274144 2020-08-19T08:45:43 Z 임성재(#5106) Mountains and Valleys (CCO20_day1problem3) C++17
2 / 25
 122 ms 110972 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;
}

Subtask #1
0.0 / 1.0

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

Subtask #2
0.0 / 2.0

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

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 110968 KB Output is correct
2 Correct 113 ms 110972 KB Output is correct
3 Correct 91 ms 110840 KB Output is correct
4 Correct 74 ms 110840 KB Output is correct
5 Correct 79 ms 110840 KB Output is correct
6 Correct 74 ms 110840 KB Output is correct
7 Correct 74 ms 110968 KB Output is correct
8 Correct 74 ms 110844 KB Output is correct
9 Correct 74 ms 110968 KB Output is correct
10 Correct 73 ms 110840 KB Output is correct
11 Correct 73 ms 110840 KB Output is correct
12 Correct 122 ms 110608 KB Output is correct
13 Correct 105 ms 110840 KB Output is correct
14 Correct 83 ms 110792 KB Output is correct

Subtask #4
0.0 / 6.0

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

Subtask #5
0.0 / 2.0

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

Subtask #6
0.0 / 3.0

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

Subtask #7
0.0 / 5.0

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

Subtask #8
0.0 / 4.0

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