Submission #393592

#TimeUsernameProblemLanguageResultExecution timeMemory
393592JimmyZJXSimurgh (IOI17_simurgh)C++14
51 / 100
295 ms4784 KiB
#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 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; bool someHasProp = has_prop(edge0); for (int j = 1; j < gp.size(); j++) { int edge = nbs[i][gp[j]].second; if (has_prop(edge)) { if (!someHasProp) someHasProp = true; else 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); } } if (!has_prop(edge0)) { // pending edge0: all pending => all set to 1 set_prop(edge0, 1); } } } 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 (stderr)

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:164:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |    for (int j = 1; j < gp.size(); j++) {
      |                    ~~^~~~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from simurgh.cpp:6:
simurgh.cpp:194:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  194 |  assert(royaleEdges.size() == n - 1);
      |         ~~~~~~~~~~~~~~~~~~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...