oj.uz

Submission #393539

# Submission time Handle Problem Language Result Execution time Memory
393539 2021-04-23T20:42:23 Z JimmyZJX Simurgh (IOI17_simurgh) C++14
0 / 100
 174 ms 4316 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <numeric>

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
typedef vector<vector<pair<int, int>>> Vip;

#define forR(i, n) for (int i = 0; i < (n); i++)

int count_common_roads(const Vi& r);

Vip nbs; // {nb, edge}
int N;
Vi pathProp; // 0: unknown; 1: royale; 2: not royale

Vi pendingEdges;

void set_prop(int e, int prop) {
	if (pathProp[e] == -1) {
		for (int pe : pendingEdges) {
			pathProp[pe] = prop;
		}
		pendingEdges.clear();
	} else {
		assert(pathProp[e] == 0 || pathProp[e] == prop);
		pathProp[e] = prop;
	}
}

void set_pending(int e1, int e2) {
	if (pendingEdges.size() > 0) {
		assert(pathProp[e1] == -1 || pathProp[e2] == -1);
	}
	if (pathProp[e1] != -1) {
		assert(pathProp[e1] == 0);
		pathProp[e1] = -1;
		pendingEdges.push_back(e1);
	}
	if (pathProp[e2] != -1) {
		assert(pathProp[e2] == 0);
		pathProp[e2] = -1;
		pendingEdges.push_back(e2);
	}
}

Vi gen_tree(int exclude, int r) {
	Vb vis(N);
	vis[exclude] = true;
	Vi edges;

	queue<int> q; q.push(r); vis[r] = true;
	while (!q.empty()) {
		int x = q.front(); q.pop();
		for (auto nb : nbs[x]) {
			if (!vis[nb.first]) {
				vis[nb.first] = true;
				q.push(nb.first);
				edges.push_back(nb.second);
			}
		}
	}

	assert(edges.size() == N - 2);
	return edges;
}

Vi find_roads(int n, Vi u, Vi v) {
	nbs = Vip(n);
	N = n;
	int m = u.size();
	pathProp = Vi(m);

	forR(i, m) {
		nbs[u[i]].push_back({ v[i], i });
		nbs[v[i]].push_back({ u[i], i });
	}

	forR(i, n) {
		if (nbs[i].size() == 1) {
			pathProp[nbs[i][0].second] = 1;
		}
	}

	Vb processed(n);
	stack<int> st;
	forR(i, n) st.push(i);
	while (!st.empty()) {
		int i = st.top(); st.pop();
		if (processed[i]) continue;
		processed[i] = true;

		Vi unknowns;
		int pIdx = -1;
		for (int j = 0; j < nbs[i].size(); j++) {
			int prop = pathProp[nbs[i][j].second];
			if (prop == -1) { // pending
				pIdx = j;
				st.push(nbs[i][j].first);
			} else if (prop == 0) { // unknown
				unknowns.push_back(j);
			}
		}
		if (unknowns.size() == 0) continue; // no unknown
		int sIdx = unknowns[0];
		if (unknowns.size() == 1) sIdx = sIdx == 0 ? 1 : 0; // only one unknown
		if (pIdx >= 0) sIdx = pIdx;

		Vi sTree = gen_tree(i, nbs[i][sIdx].first);
		int sEdge = nbs[i][sIdx].second;
		sTree.push_back(sEdge); // n-1 edges
		int sVal = count_common_roads(sTree);
		sTree.pop_back();

		for (int j = 0; j < nbs[i].size(); j++) {
			int prop = pathProp[nbs[i][j].second];
			if (j == sIdx || prop > 0) continue;

			int jEdge = nbs[i][j].second;
			sTree.push_back(jEdge);
			int jVal = count_common_roads(sTree);
			sTree.pop_back();

			if (jVal == sVal) {
				if (pathProp[sEdge] == -1) {
					set_pending(sEdge, jEdge);
					st.push(nbs[i][j].first);
				} else {
					set_prop(jEdge, pathProp[sEdge]);
				}
			} else if (jVal < sVal) {
				set_prop(jEdge, 2);
				set_prop(sEdge, 1); // royale
			} else { // jVal > sVal
				set_prop(jEdge, 1); // royale
				set_prop(sEdge, 2);
			}
		}
	}

	int cntRoyale = 0;
	forR(i, m) if (pathProp[i] == 1) cntRoyale++;

	if (pendingEdges.size() > 0) {
		if (cntRoyale < n - 1) {
			cntRoyale += pendingEdges.size();
			set_prop(pendingEdges[0], 1);
		}
	}
	assert(cntRoyale == n - 1);

	Vi royaleEdges;
	forR(i, m) if (pathProp[i] == 1) royaleEdges.push_back(i);
	return royaleEdges;
}


#ifdef TEST_LOCAL
set<int> _ry{ 5,1,0 };
int count_common_roads(const Vi& r) {
	int cnt = 0;
	for (int e : r)
		if (_ry.count(e) > 0)
			cnt++;
	return cnt;
}

int main() {
	auto r = find_roads(4, Vi{ 0, 0, 0, 1, 1, 2 }, Vi{ 1, 2, 3, 2, 3, 3 });

	return 0;
}
#endif

Compilation message

In file included from /usr/include/c++/9/cassert:44,
                 from simurgh.cpp:6:
simurgh.cpp: In function 'Vi gen_tree(int, int)':
simurgh.cpp:82:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |  assert(edges.size() == N - 2);
      |         ~~~~~~~~~~~~~^~~~~~~~
simurgh.cpp: In function 'Vi find_roads(int, Vi, Vi)':
simurgh.cpp:113:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |   for (int j = 0; j < nbs[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~
simurgh.cpp:133:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |   for (int j = 0; j < nbs[i].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 208 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 296 KB correct
10 Correct 1 ms 204 KB correct
11 Runtime error 1 ms 460 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 208 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 296 KB correct
10 Correct 1 ms 204 KB correct
11 Runtime error 1 ms 460 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 208 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 296 KB correct
10 Correct 1 ms 204 KB correct
11 Runtime error 1 ms 460 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB correct
2 Correct 1 ms 204 KB correct
3 Incorrect 174 ms 4316 KB WA in grader: NO
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB correct
2 Correct 1 ms 204 KB correct
3 Correct 1 ms 204 KB correct
4 Correct 1 ms 204 KB correct
5 Correct 1 ms 204 KB correct
6 Correct 1 ms 204 KB correct
7 Correct 1 ms 208 KB correct
8 Correct 1 ms 204 KB correct
9 Correct 1 ms 296 KB correct
10 Correct 1 ms 204 KB correct
11 Runtime error 1 ms 460 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -