oj.uz

Submission #309671

# Submission time Handle Problem Language Result Execution time Memory
309671 2020-10-04T06:53:50 Z Akashi Training (IOI07_training) C++14
0 / 100
 21 ms 640 KB 
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

const int DIM = 1e3 + 5;

struct drum {
	int x, y, c;
};

int n, m;

int tt[DIM], h[DIM], dp[DIM];
bool viz[DIM];
int mark[DIM];
vector <int> arb[DIM];
vector <pair <int, int>> v[DIM];
vector <drum> path[DIM];

vector <int> l;

int lca(int x, int y) {
	while (x != y) {
		if (h[x] > h[y]) x = tt[x];
		else y = tt[y];
	}
	return x;
}

bool mark_road(int nod, int now) {
	if (now == nod) return true;
	l.push_back(now);
	++mark[now];
	if (mark[now] >= 2) return false;
	return mark_road(nod, tt[now]);
}

void unmark_road(int sz) {
	if ((int)l.size() == sz) return ;
	--mark[l.back()];
	l.pop_back();
	unmark_road(sz);
}

void back(int ind, int nod, int end, int sum = 0) {
	if (ind == end) {
		for (auto cur : l) {
			for (auto fiu : arb[cur]) {
				if (fiu != tt[cur] && !mark[fiu])
					sum = sum + dp[fiu];
			}
		}

		dp[nod] = max(dp[nod], sum);
		return ;
	}

	int sz = l.size();
	back(ind + 1, nod, end, sum);

	bool ok = mark_road(nod, v[nod][ind].x);
	if (ok)
	back(ind + 1, nod, end, sum + v[nod][ind].y);

	unmark_road(sz);
}

void dfs(int nod = 1, int papa = 0) {
	for (auto it : arb[nod]) {
		if (it == papa) continue ;
		h[it] = h[nod] + 1;
		dfs(it, nod);
		tt[it] = nod;
	}
}

void solve(int nod = 1, int papa = 0) {
	for (auto it : arb[nod]) {
		if (it == papa) continue ;
		solve(it, nod);
		dp[nod] += dp[it];
	}

	back(0, nod, v[nod].size(), 0);
	for (auto it : path[nod]) {
		mark_road(nod, it.x); mark_road(nod, it.y);
		back(0, nod, v[nod].size(), it.c + dp[it.x] + dp[it.y]);
		unmark_road(0);
	}
}

int main() {
	scanf("%d%d", &n, &m);

	int x, y, c;
	int sum = 0;

	vector <tuple<int, int, int>> edges;

	for (int i = 1; i <= m ; ++i) {
		scanf("%d%d%d", &x, &y, &c);
		
		if (c == 0) {
			arb[x].push_back(y);
			arb[y].push_back(x);
		} else {
			edges.push_back({x, y, c});
		}	
	}

	dfs();
	
	for (auto it : edges) {
		x = get<0>(it);
		y = get<1>(it);
		c = get<2>(it);

		sum += c;

		int z = lca(x, y);
		if ((h[x] - h[z] + h[y] - h[z] + 1) % 2 == 0) continue ;
	
		if (z == x) v[z].push_back({y, c});
		else if (z == y) v[z].push_back({x, c});
		else 	path[z].push_back({x, y, c});
	}

	solve();
	for (int i = 1; i <= n ; ++i) cerr << dp[i] << " ";
	cerr << endl;
	printf("%d", sum - dp[1]);
	return 0;
}

Compilation message

training.cpp: In function 'int main()':
training.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
training.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |   scanf("%d%d%d", &x, &y, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -