oj.uz

Submission #309674

# Submission time Handle Problem Language Result Execution time Memory
309674 2020-10-04T07:11:24 Z Akashi Training (IOI07_training) C++14
30 / 100
 300 ms 836 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 <drum> v[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) {
			
			int ad = 0;
			bool tip = 1;

			for (auto fiu : arb[cur]) {
				if (fiu != tt[cur] && !mark[fiu])
					ad = ad + dp[fiu];
				if (fiu != tt[cur] && mark[fiu]) tip = 0;
			}

			if (tip) sum = sum + max(ad, dp[cur]);
			else sum = sum + ad;
		}

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

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

	bool ok1 = mark_road(nod, v[nod][ind].x);
	bool ok2 = mark_road(nod, v[nod][ind].y);

	if (ok1 & ok2)
	back(ind + 1, nod, end, sum + v[nod][ind].c);

	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);
}

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, z, c});
		else if (z == y) v[z].push_back({x, z, c});
		else v[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:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
training.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |   scanf("%d%d%d", &x, &y, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 564 KB Output is correct
2 Correct 26 ms 632 KB Output is correct

Subtask #4
0 / 7.0

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

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 62 ms 516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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