| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 393538 | JimmyZJX | Simurgh (IOI17_simurgh) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(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(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