제출 #826904

#제출 시각아이디문제언어결과실행 시간메모리
826904ymm열쇠 (IOI21_keys)C++17
37 / 100
366 ms133204 KiB
#include <bits/stdc++.h> #define Loop(x,l,r) for (ll x = (l); x < (r); ++x) typedef long long ll; typedef std::pair<int,int> pii; using namespace std; const int N = 300'010; vector<pii> A[N]; int key[N]; template<class T> void clear_and_free(T &x) { T tmp; tmp.swap(x); } namespace dsu { struct cmp_t { int vis; cmp_t *par; vector<int> nds; vector<int> adj; map<int,vector<int>> if_had_key; set<int> keys; bool not_sink; int cost; } cmp[N]; void init(int n) { Loop (i,0,n) { auto *c = &cmp[i]; c->vis = 0; c->par = 0; c->nds = {(int)i}; for (auto [v, k] : A[i]) { if (k == key[i]) c->adj.push_back(v); else c->if_had_key[k].push_back(v); } c->keys = {key[i]}; c->not_sink = 0; c->cost = 5 + A[i].size(); } } cmp_t *rt(cmp_t *c) { return c->par? (c->par = rt(c->par)): c; } cmp_t *rt(int v) { return rt(&cmp[v]); } void merge(cmp_t *c, cmp_t *d) { c = rt(c); d = rt(d); if (c == d) return; //cerr << "merge(" << c-cmp << ", " << d-cmp << ")\n"; if (c->cost < d->cost) swap(c, d); c->cost += d->cost; c->nds.insert(c->nds.end(), d->nds.begin(), d->nds.end()); c->adj.insert(c->adj.end(), d->adj.begin(), d->adj.end()); for (auto k : d->keys) c->cost -= 4*!c->keys.insert(k).second; for (auto &[k, vec] : d->if_had_key) { if (c->keys.count(k)) { c->adj.insert(c->adj.end(), vec.begin(), vec.end()); } else { auto &tmp = c->if_had_key[k]; tmp.insert(tmp.end(), vec.begin(), vec.end()); } } for (auto k : d->keys) { auto &vec = c->if_had_key[k]; c->adj.insert(c->adj.end(), vec.begin(), vec.end()); clear_and_free(vec); } d->par = c; clear_and_free(d->nds); clear_and_free(d->adj); clear_and_free(d->if_had_key); clear_and_free(d->keys); } } typedef dsu::cmp_t *cmp; void dfs(cmp v, int t) { vector<cmp> anc; anc.push_back(v); v->vis = t; for (;;) { cmp v = dsu::rt(anc.back()); if (v->adj.size()) { auto u = dsu::rt(v->adj.back()); v->adj.pop_back(); v->cost--; if (u == v) continue; //cerr << v-dsu::cmp << " -> " << u-dsu::cmp << '\n'; if (u->vis == t) { while (dsu::rt(v) != dsu::rt(u)) { auto x = dsu::rt(anc.back()); anc.pop_back(); auto y = dsu::rt(anc.back()); anc.pop_back(); dsu::merge(x, y); anc.push_back(dsu::rt(x)); } } else if (u->vis) { for (auto v : anc) rt(v)->not_sink = 1; return; } else { u->vis = t; anc.push_back(u); } } else { anc.pop_back(); for (auto v : anc) rt(v)->not_sink = 1; return; } } } std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) { int n = r.size(); int m = u.size(); Loop (i,0,n) key[i] = r[i]; Loop (i,0,m) { int x = v[i], y = u[i], z = c[i]; A[x].emplace_back(y, z); A[y].emplace_back(x, z); } dsu::init(n); int nxt = 1; Loop (i,0,n) { cmp c = &dsu::cmp[i]; if (c->par) continue; dfs(c, nxt++); } int mn = N; Loop (i,0,n) { cmp c = &dsu::cmp[i]; if (c->par || c->not_sink) continue; mn = min<int>(mn, c->nds.size()); } vector<int> ans(n); Loop (i,0,n) { cmp c = &dsu::cmp[i]; if (c->par || c->not_sink) continue; if (c->nds.size() != mn) continue; for (auto x : c->nds) ans[x] = 1; } return ans; }

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

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:150:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |   if (c->nds.size() != mn)
      |       ~~~~~~~~~~~~~~^~~~~
#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...