제출 #491745

#제출 시각아이디문제언어결과실행 시간메모리
491745maksim1744열쇠 (IOI21_keys)C++17
37 / 100
3091 ms36528 KiB
/* author: Maksim1744 created: 04.12.2021 11:30:50 */ #include "bits/stdc++.h" using namespace std; using ll = long long; using ld = long double; #define mp make_pair #define pb push_back #define eb emplace_back #define sum(a) ( accumulate ((a).begin(), (a).end(), 0ll)) #define mine(a) (*min_element((a).begin(), (a).end())) #define maxe(a) (*max_element((a).begin(), (a).end())) #define mini(a) ( min_element((a).begin(), (a).end()) - (a).begin()) #define maxi(a) ( max_element((a).begin(), (a).end()) - (a).begin()) #define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin()) #define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin()) template<typename T> vector<T>& operator-- (vector<T> &v){for (auto& i : v) --i; return v;} template<typename T> vector<T>& operator++ (vector<T> &v){for (auto& i : v) ++i; return v;} template<typename T> istream& operator>>(istream& is, vector<T> &v){for (auto& i : v) is >> i; return is;} template<typename T> ostream& operator<<(ostream& os, vector<T> v){for (auto& i : v) os << i << ' '; return os;} template<typename T, typename U> pair<T,U>& operator-- (pair<T, U> &p){--p.first; --p.second; return p;} template<typename T, typename U> pair<T,U>& operator++ (pair<T, U> &p){++p.first; ++p.second; return p;} template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second; return is;} template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U> p){os << p.first << ' ' << p.second; return os;} template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);} template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);} template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;} template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;} #ifdef HOME #define SHOW_COLORS #include "/mnt/c/Libs/tools/print.cpp" #else #define show(...) void(0) #define debugf(fun) fun #define debugv(var) var #define mclock void(0) #define shows void(0) #define debug if (false) #endif vector<int> scc(vector<vector<int>>& g) { int n = g.size(); vector<int> topsort; topsort.reserve(n); vector<bool> u(n, false); function<void(int)> scc_dfs1 = [&](int v) { u[v] = true; for (auto k : g[v]) if (!u[k]) scc_dfs1(k); topsort.push_back(v); }; for (int i = 0; i < n; ++i) if (!u[i]) scc_dfs1(i); vector<vector<int>> gi(n); for (int i = 0; i < n; ++i) for (auto j : g[i]) gi[j].push_back(i); int color = 0; vector<int> comp(n, -1); reverse(topsort.begin(), topsort.end()); function<void(int, int)> scc_dfs2 = [&](int v, int color) { comp[v] = color; for (auto k : gi[v]) if (comp[k] == -1) scc_dfs2(k, color); }; for (auto v : topsort) if (comp[v] == -1) scc_dfs2(v, color++); return comp; } vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) { int n = r.size(); vector<vector<pair<int, pair<int, int>>>> g(n); for (int i = 0; i < u.size(); ++i) { g[u[i]].eb(v[i], mp(i * 2 + 0, c[i])); g[v[i]].eb(u[i], mp(i * 2 + 1, c[i])); } vector<vector<int>> go(n); vector<bool> ue(u.size() * 2, false); bool because_change = false; for (int iter = 0; iter < 1e9; ++iter) { bool change = false; auto col = scc(go); vector<vector<int>> comps(maxe(col) + 1); for (int i = 0; i < n; ++i) { comps[col[i]].pb(i); } for (int i = 0; i < comps.size(); ++i) { set<int> cur; for (int v : comps[i]) { cur.insert(r[v]); } for (int v : comps[i]) { for (auto [u, ic] : g[v]) { auto [ind, c] = ic; if (col[u] == col[v]) continue; if (!cur.count(c)) continue; if (ue[ind]) continue; ue[ind] = true; go[v].pb(u); change = true; } } } show(go, change); if (!change) { because_change = true; break; } } auto col = scc(go); vector<bool> terminal(maxe(col) + 1, true); for (int i = 0; i < n; ++i) { for (auto j : go[i]) { if (col[i] == col[j]) continue; terminal[col[i]] = false; } } show(go); show(col); show(terminal); vector<int> sz(terminal.size(), 1e9); auto reachable = [&](int v) { queue<int> q; int ans = 0; q.push(v); map<int, vector<int>> tos; set<int> has; vector<bool> u(n, false); while (!q.empty()) { auto v = q.front(); q.pop(); if (u[v]) continue; u[v] = true; ++ans; if (!has.count(r[v])) { has.insert(r[v]); for (int k : tos[r[v]]) q.push(k); tos.erase(r[v]); } for (auto [k, ic] : g[v]) { auto [ind, c] = ic; if (has.count(c)) q.push(k); else tos[c].pb(k); } } show(v, ans); return ans; }; if (because_change) { for (int i = 0; i < n; ++i) { if (terminal[col[i]]) sz[col[i]] = 0; } for (int i = 0; i < n; ++i) { sz[col[i]]++; } } else { vector<int> check; for (int i = 0; i < n; ++i) { if (terminal[col[i]]) { terminal[col[i]] = false; check.pb(i); } } for (int v : check) { sz[col[v]] = reachable(v); } } show(sz); vector<int> ans(n, 0); int mnsz = mine(sz); for (int i = 0; i < n; ++i) { if (sz[col[i]] == mnsz) { ans[i] = 1; } } return ans; } #ifdef HOUSE int main() { int n, m; assert(2 == scanf("%d%d", &n, &m)); std::vector<int> r(n), u(m), v(m), c(m); for(int i=0; i<n; i++) { assert(1 == scanf("%d", &r[i])); } for(int i=0; i<m; i++) { assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i])); } fclose(stdin); std::vector<int> ans = find_reachable(r, u, v, c); for (int i = 0; i < (int) ans.size(); ++i) { if(i) putchar(' '); putchar(ans[i]+'0'); } printf("\n"); return 0; } #endif

컴파일 시 표준 에러 (stderr) 메시지

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i = 0; i < u.size(); ++i) {
      |                     ~~^~~~~~~~~~
keys.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for (int i = 0; i < comps.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~
#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...