oj.uz

답안 #753670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753670 2023-06-05T16:45:26 Z lukameladze Training (IOI07_training) C++14
0 / 100
 16 ms 6612 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
 #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 5005;
int t,n,m,a[N],in[N],out[N],tin, dp[N][1025],id[N][N];
int par[N],lv[N];
vector <int> v[N];
void dfs(int a, int p) {
	in[a] = ++tin;
	par[a] = p;
	lv[a] = lv[p] + 1;
	for (int to : v[a]) {
		if (to == p) continue;
		dfs(to, a);
	}
	out[a] = tin;
}
int upper(int a, int b) {
	return (in[a] <= in[b] && out[a] >= out[b]);
}
int lca(int a, int b) {
	int cur = a;
	while (!upper(cur, b)) {
		cur = par[cur];
	}
	return cur;
}
int get(int a, int p) {
	int cur = a, lst = -1, ans = 0;
	while (cur != p) {
		if (lst == -1) ans += dp[cur][0];
		else ans += dp[cur][id[cur][lst]];
		lst = cur;
		cur = par[cur];
	}
	return ans;
}
vector <array <int, 3> > g[N];
int kth(int x, int k) {
	while (k--) {
		x = par[x];
	}
	return x;
}
void dfs1(int a, int p) {
	int cnt = 0;
	for (int to : v[a]) {
		if (to == p) continue;
		id[a][to] = cnt;
		cnt++;
		dfs1(to, a);
	}
	vector <array <int, 4> > pot;
	for (array <int, 3> edge : g[a]) {
		int x = edge[0], y = edge[1], z = edge[2];
		int msk = 0;
		if (a != x) {
			int getx = kth(x, lv[x] - lv[a] - 1);
			msk |= (1<<id[a][getx]);
		} 

		if (a != y) {
			int gety = kth(y, lv[y] - lv[a] - 1);
			msk |= (1<<id[a][gety]);
		}

		pot.pb({x, y, z, msk});
	}
	for (array <int, 4> edge : pot) {
		int x = edge[0], y = edge[1], z = edge[2], cur_mask = edge[3];
		
		for (int msk = (1<<cnt) - 1; msk >= 0; msk--) {
			if ((msk & cur_mask)) continue;
			int cur_pas = dp[a][msk | cur_mask]; // add (x -- y) wibo
			cur_pas += get(x, a) + get(y, a) + z;
			dp[a][msk] = max(dp[a][msk], cur_pas);
		}
	}
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	vector < array <int, 3 > > vec, vn;
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		cin>>a>>b>>c;
		if (c == 0) {
			v[a].pb(b);
			v[b].pb(a);
		} else {
			vec.pb({a, b, c});
		}
	}
	dfs(1, 0);
	for (array <int, 3> x : vec) {
		int a = x[0], b = x[1], c = x[2];
		int dist = lv[a] + lv[b] - 2 * lv[lca(a, b)];
		if (dist % 2 == 1) { 
		} else vn.pb(x);
	}
	vec = vn;
	for (array <int, 3> x : vec) {
		int a = x[0], b = x[1], c = x[2];
		g[lca(a, b)].pb({a,b,c});
	}
	dfs1(1, 0);
	cout<<dp[1][0]<<"\n";
}

Compilation message

training.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   84 | main() {
      | ^~~~
training.cpp: In function 'int main()':
training.cpp:100:27: warning: unused variable 'c' [-Wunused-variable]
  100 |   int a = x[0], b = x[1], c = x[2];
      |                           ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 6612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 4436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 3936 KB Output isn't correct
2 Halted 0 ms 0 KB -