oj.uz

Submission #395566

# Submission time Handle Problem Language Result Execution time Memory
395566 2021-04-28T14:38:58 Z Berted Training (IOI07_training) C++14
100 / 100
 82 ms 31300 KB 
#include <iostream>
#include <vector>
#include <algorithm>

#define vi vector<int>
#define pii pair<int, int>
#define ppi pair<pii, int>
#define fst first
#define snd second

const int INF = 1e8;

using namespace std;

int N, M; 
vector<pii> adj[1001]; pii par[1001]; int H[1001];
vi child[1001];
vector<ppi> edges, tp;

vector<ppi> finish[1001];
vector<int> mem[1001]; int cst[1001];
int res = 0, DP[1001][5001], temp[1001][1024];

void DFS1(int u)
{
	//cerr << "D1: " << u << " " << H[u] << " " << par[u].fst << ", " << par[u].snd << "\n";
	for (const pii &v : adj[u])
	{
		if (v.fst != par[u].fst)
		{
			H[v.fst] = H[u] + 1;
			par[v.fst] = {u, v.snd};
			child[u].push_back(v.fst);
			DFS1(v.fst);
		}
	}
}

void DFS2(int u)
{
	for (const int &v : child[u]) {DFS2(v);}
	int S = child[u].size();

	//cerr << "D2: " << u << "\n";

	for (int i = 0; i <= edges.size(); i++) DP[u][i] = INF;
	for (int i = 0; i < (1 << S); i++) temp[u][i] = INF;
	temp[u][0] = 0;

	//cerr << "SET " << S << "\n";

	for (int i = 1; i < (1 << S); i++)
	{
		for (const auto &p : finish[u])
		{
			int i1 = p.fst.fst, M1 = (i1 == -1) ? 0 : (1 << i1), c1 = (i1 == -1) ? 0 : DP[child[u][i1]][p.snd];
			int i2 = p.fst.snd, M2 = (i2 == -1) ? 0 : (1 << i2), c2 = (i2 == -1) ? 0 : DP[child[u][i2]][p.snd];
			if ((i & (M1 | M2)) == (M1 | M2))
			{
				temp[u][i] = min(temp[u][i], temp[u][i ^ (M1 | M2)] + c1 + c2);
			}
		}
		for (int j = 0; j < S; j++)
		{
			if (i & (1 << j)) temp[u][i] = min(temp[u][i], temp[u][i ^ (1 << j)] + DP[child[u][j]][0]);
		}
		//cerr << temp[u][i] << " ";
	}
	//cerr << "\n";

	//cerr << "TEMP\n";

	if (par[u].snd != -1)
	{

		int j = 0, p = par[u].snd;
		DP[u][0] = temp[u][(1 << S) - 1] + cst[p];

		//cerr << "P: " << p << " " << cst[p] << " " << DP[u][0] << "\n";
		for (int i = 1; i <= edges.size(); i++)
		{
			int c = (edges[i - 1].fst.snd == u) ? edges[i - 1].snd : 0;
			for (; j < mem[p].size() && mem[p][j] / N < i; j++);
			if (j < mem[p].size() && mem[p][j] / N == i)
			{
				int x = mem[p][j] % N;
				//cerr << i << " " << j << " " << x << "\n";
				if (child[u].size() == 0) {x = -1;}
				for (int k = 0; k < child[u].size(); k++)
				{
					if (child[u][k] == x) {x = k; break;}
					else if (k + 1 == child[u].size()) {x = -1;}
				}
				if (x == -1) {DP[u][i] = temp[u][(1 << S) - 1] + cst[p] - c;}
				else {DP[u][i] = temp[u][((1 << S) - 1) ^ (1 << x)] + DP[child[u][x]][i] + cst[p] - c;}
				j++;
			}
			//cerr << i << " " << c << ": " << DP[u][i] << "\n";
		}
	}
	else {DP[u][0] = temp[u][(1 << S) - 1];}

	//cerr << "DP\n";
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int u, v, c; cin >> u >> v >> c; u--; v--;
		if (c) {tp.push_back({{u, v}, c});}
		else
		{
			int id = i - tp.size();
			adj[u].push_back({v, id});
			adj[v].push_back({u, id});
		}
	}

	for (int i = 0; i < N; i++) sort(adj[i].begin(), adj[i].end());

	par[0] = {-1, -1}; H[0] = 0;
	DFS1(0);
	
	for (const ppi &v : tp)
	{
		if ((H[v.fst.fst] ^ H[v.fst.snd]) & 1) {res += v.snd;}
		else {edges.push_back(v);}
	}

	for (int i = 0; i < edges.size(); i++) 
	{
		if (H[edges[i].fst.fst] > H[edges[i].fst.snd]) swap(edges[i].fst.fst, edges[i].fst.snd);
		int u = edges[i].fst.fst, v = edges[i].fst.snd, pu = u, pv = v, c = edges[i].snd;
		cst[par[v].snd] += c;

		while (H[v] > H[u]) {mem[par[v].snd].push_back((i + 1) * N + pv); pv = v; v = par[v].fst;}
		while (u != v) 
		{
			mem[par[u].snd].push_back((i + 1) * N + pu); pu = u; u = par[u].fst;
			mem[par[v].snd].push_back((i + 1) * N + pv); pv = v; v = par[v].fst;
		}
		//cerr << u << " " << v << " " << pu << " " << pv << "\n";
		for (int j = 0; j < child[u].size(); j++)
		{
			if (pu == child[u][j]) {pu = j; break;}
			else if (j + 1 == child[u].size()) {pu = -1;}
		}
		for (int j = 0; j < child[u].size(); j++)
		{
			if (pv == child[u][j]) {pv = j; break;}
			else if (j + 1 == child[u].size()) {pv = -1;}
		}
		//cerr << u << " " << v << " push: " << pu << " " << pv << " " << i + 1 << "\n";
		finish[u].push_back({{pu, pv}, i + 1});
	}

	DFS2(0); res += DP[0][0]; 
	cout << res << "\n";
	return 0;
}

Compilation message

training.cpp: In function 'void DFS2(int)':
training.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i = 0; i <= edges.size(); i++) DP[u][i] = INF;
      |                  ~~^~~~~~~~~~~~~~~
training.cpp:80:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int i = 1; i <= edges.size(); i++)
      |                   ~~^~~~~~~~~~~~~~~
training.cpp:83:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    for (; j < mem[p].size() && mem[p][j] / N < i; j++);
      |           ~~^~~~~~~~~~~~~~~
training.cpp:84:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    if (j < mem[p].size() && mem[p][j] / N == i)
      |        ~~^~~~~~~~~~~~~~~
training.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int k = 0; k < child[u].size(); k++)
      |                     ~~^~~~~~~~~~~~~~~~~
training.cpp:92:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |      else if (k + 1 == child[u].size()) {x = -1;}
      |               ~~~~~~^~~~~~~~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:133:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |  for (int i = 0; i < edges.size(); i++)
      |                  ~~^~~~~~~~~~~~~~
training.cpp:146:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for (int j = 0; j < child[u].size(); j++)
      |                   ~~^~~~~~~~~~~~~~~~~
training.cpp:149:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |    else if (j + 1 == child[u].size()) {pu = -1;}
      |             ~~~~~~^~~~~~~~~~~~~~~~~~
training.cpp:151:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |   for (int j = 0; j < child[u].size(); j++)
      |                   ~~^~~~~~~~~~~~~~~~~
training.cpp:154:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |    else if (j + 1 == child[u].size()) {pv = -1;}
      |             ~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 14380 KB Output is correct
2 Correct 29 ms 15484 KB Output is correct

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3504 KB Output is correct
2 Correct 5 ms 3660 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8116 KB Output is correct
2 Correct 12 ms 7960 KB Output is correct
3 Correct 17 ms 8012 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 22724 KB Output is correct
2 Correct 44 ms 21676 KB Output is correct
3 Correct 46 ms 23364 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7628 KB Output is correct
2 Correct 16 ms 8652 KB Output is correct
3 Correct 63 ms 31072 KB Output is correct
4 Correct 17 ms 9108 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 26440 KB Output is correct
2 Correct 82 ms 31300 KB Output is correct
3 Correct 58 ms 26348 KB Output is correct
4 Correct 50 ms 23856 KB Output is correct