#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<vector<int>>> Viii;
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}
Viii nbgps; // index
int N;
Vi pathProp; // 0: unknown; 1: royale; 2: not royale
Vb pathPending;
Vi parent; // disjoint set
int getRoot(int x) {
if (x == parent[x]) return x;
int ppx = getRoot(parent[x]);
parent[x] = ppx;
return ppx;
}
void setEq(int x, int y) {
int px = getRoot(x), py = getRoot(y);
parent[py] = px;
if (pathProp[py] > 0) {
assert(pathProp[px] == 0 || pathProp[px] == pathProp[py]);
pathProp[px] = pathProp[py];
}
pathPending[px] = pathPending[py] = true;
}
void set_prop(int e, int prop) {
int re = getRoot(e);
assert(pathProp[re] == 0 || pathProp[re] == prop);
pathProp[re] = prop;
}
int get_prop(int e) {
int re = getRoot(e);
assert(pathProp[re] > 0);
return pathProp[re];
}
bool has_prop(int e) {
int re = getRoot(e);
return pathPending[e] || pathProp[re] > 0;
}
pair<Vi, Vb> gen_tree(int root, int node = -1) {
Vb vis(N); vis[root] = true;
queue<int> q;
if (node < 0) {
for (auto& gps : nbgps[root]) {
int node = nbs[root][gps[0]].first;
vis[node] = true;
q.push(node);
}
} else {
vis[node] = true;
q.push(node);
}
Vi edges;
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);
}
}
}
if (node < 0) {
assert(edges.size() == N - 1 - nbgps[root].size());
}
return { edges, vis };
}
Vi find_roads(int n, Vi u, Vi v) {
nbs = Vip(n);
nbgps = Viii(n);
N = n;
int m = u.size();
pathProp = Vi(m);
pathPending = Vb(m);
parent = Vi();
forR(i, m) parent.push_back(i);
forR(i, m) {
nbs[u[i]].push_back({ v[i], i });
nbs[v[i]].push_back({ u[i], i });
}
forR(i, n) {
Vb visited(n);
forR(j, nbs[i].size()) {
int node = nbs[i][j].first;
if (visited[node]) continue;
auto pair = gen_tree(i, node);
Vb& vis = pair.second;
nbgps[i].push_back(Vi());
forR(k, nbs[i].size()) {
int nk = nbs[i][k].first;
if (vis[nk]) {
nbgps[i].back().push_back(k);
visited[nk] = true;
}
}
}
}
forR(i, n) {
Vi sTree = gen_tree(i).first;
Vi sTree0 = sTree; // all first edges
forR(k, nbgps[i].size()) {
int edge = nbs[i][nbgps[i][k][0]].second;
sTree0.push_back(edge);
}
int val0 = count_common_roads(sTree0);
forR(igp, nbgps[i].size()) {
auto& gp = nbgps[i][igp];
if (gp.size() == 1) {
set_prop(nbs[i][gp[0]].second, 1);
continue;
}
Vi gpTree = sTree;
forR(k, nbgps[i].size()) { // edges of other groups
if (k == igp) continue;
int edge = nbs[i][nbgps[i][k][0]].second;
gpTree.push_back(edge);
}
int edge0 = nbs[i][gp[0]].second;
for (int j = 1; j < gp.size(); j++) {
int edge = nbs[i][gp[j]].second;
if (has_prop(edge)) continue;
gpTree.push_back(edge);
int valJ = count_common_roads(gpTree);
gpTree.pop_back();
if (val0 == valJ) {
setEq(edge0, edge);
} else if (val0 < valJ) { // j royale
set_prop(edge0, 2);
set_prop(edge, 1);
} else { // 0 royale
set_prop(edge0, 1);
set_prop(edge, 2);
}
}
}
}
Vi royaleEdges;
forR(i, m) if (get_prop(i) == 1) royaleEdges.push_back(i);
assert(royaleEdges.size() == n - 1);
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, 3, 2, 3 }); //
return 0;
}
#endif
Compilation message
simurgh.cpp: In function 'Vi find_roads(int, Vi, Vi)':
simurgh.cpp:28:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | #define forR(i, n) for (int i = 0; i < (n); i++)
| ^
simurgh.cpp:120:3: note: in expansion of macro 'forR'
120 | forR(j, nbs[i].size()) {
| ^~~~
simurgh.cpp:28:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | #define forR(i, n) for (int i = 0; i < (n); i++)
| ^
simurgh.cpp:127:4: note: in expansion of macro 'forR'
127 | forR(k, nbs[i].size()) {
| ^~~~
simurgh.cpp:28:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | #define forR(i, n) for (int i = 0; i < (n); i++)
| ^
simurgh.cpp:141:3: note: in expansion of macro 'forR'
141 | forR(k, nbgps[i].size()) {
| ^~~~
simurgh.cpp:28:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | #define forR(i, n) for (int i = 0; i < (n); i++)
| ^
simurgh.cpp:147:3: note: in expansion of macro 'forR'
147 | forR(igp, nbgps[i].size()) {
| ^~~~
simurgh.cpp:28:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | #define forR(i, n) for (int i = 0; i < (n); i++)
| ^
simurgh.cpp:155:4: note: in expansion of macro 'forR'
155 | forR(k, nbgps[i].size()) { // edges of other groups
| ^~~~
simurgh.cpp:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
162 | for (int j = 1; j < gp.size(); j++) {
| ~~^~~~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
from simurgh.cpp:6:
simurgh.cpp:185:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
185 | assert(royaleEdges.size() == n - 1);
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
correct |
| 2 |
Correct |
1 ms |
204 KB |
correct |
| 3 |
Incorrect |
300 ms |
4708 KB |
WA in grader: NO |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
