oj.uz

Submission #119717

# Submission time Handle Problem Language Result Execution time Memory
119717 2019-06-22T01:06:56 Z eriksuenderhauf Training (IOI07_training) C++11
100 / 100
 17 ms 4608 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e3 + 5;
const double eps = 1e-9;
vi adj[MAXN];
vector<pair<int,pii>> edg;
int par[11][MAXN], depth[MAXN], en[MAXN];
pii pa[MAXN];
int t = 0, dp[MAXN][1030], deg[MAXN];

void dfs(int u, int p) {
	t++;
	for (int v: adj[u]) {
		if (v == p)
			continue;
		depth[v] = depth[u] + 1;
		par[0][v] = u;
		pa[v] = mp(u, 1 << deg[u]++);
		dfs(v, u);
	}
	en[u] = ++t;
}

int lca(int u, int v) {
	if (depth[u] > depth[v])
		swap(u, v);
	int d = depth[v] - depth[u];
	for (int i = 10; i >= 0; i--)
		if ((d >> i) & 1)
			v = par[i][v];
	if (v == u) return v;
	for (int i = 10; i >= 0; i--)
		if (par[i][v] != par[i][u])
			v = par[i][v], u = par[i][u];
	return par[0][u];
}

int dist(int u, int v, int l = -1) {
	if (l == -1) l = lca(u, v);
	return depth[u] + depth[v] - 2 * depth[l];
}

int main() {
	int n, m, sm = 0;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int u,v,w;
		scanf("%d %d %d", &u, &v, &w);
		sm += w;
		u--, v--;
		if (w == 0) {
			adj[u].pb(v);
			adj[v].pb(u);
		}
		edg.pb(mp(w, mp(u,v)));
	}
	pa[0] = mp(-1, -1);
	dfs(0, -1);
	for (int i = 1; i < 11; i++)
		for (int j = 0; j < n; j++)
			par[i][j] = par[i-1][par[i-1][j]];
	sort(edg.begin(), edg.end(), [](pair<int,pii> l, pair<int,pii> r) {
		return en[lca(l.se.fi, l.se.se)] < en[lca(r.se.fi, r.se.se)];
	});
	for (int i = 0; i < m; i++) {
		int l = lca(edg[i].se.fi, edg[i].se.se);
		if (edg[i].fi != 0 && (dist(edg[i].se.fi, edg[i].se.se, l) & 1))
			continue;
		pii u, v;
		int cur = edg[i].fi;
		for (u = mp(edg[i].se.fi, 0); u.fi != l; u = pa[u.fi]) cur += dp[u.fi][u.se];
		for (v = mp(edg[i].se.se, 0); v.fi != l; v = pa[v.fi]) cur += dp[v.fi][v.se];
		for (int msk = (1 << deg[l]) - 1; msk >= 0; msk--)
			if (!(msk & u.se || msk & v.se))
				dp[l][msk] = max(dp[l][msk], cur + dp[l][msk | u.se | v.se]);
	}
	pri(sm - dp[0][0]);
    return 0;
}

Compilation message

training.cpp: In function 'int main()':
training.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
training.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4480 KB Output is correct
2 Correct 11 ms 4608 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 640 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 4 ms 768 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1152 KB Output is correct
2 Correct 6 ms 896 KB Output is correct
3 Correct 7 ms 1536 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2176 KB Output is correct
2 Correct 10 ms 1316 KB Output is correct
3 Correct 8 ms 1536 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 7 ms 1664 KB Output is correct
3 Correct 17 ms 4608 KB Output is correct
4 Correct 7 ms 1764 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2176 KB Output is correct
2 Correct 15 ms 4604 KB Output is correct
3 Correct 11 ms 1664 KB Output is correct
4 Correct 10 ms 1536 KB Output is correct