제출 #1059396

#제출 시각아이디문제언어결과실행 시간메모리
1059396Trent열쇠 (IOI21_keys)C++17
9 / 100
1066 ms645996 KiB
#include "bits/stdc++.h" using namespace std; #define forR(i, x) for(int i = 0; i < (x); ++i) #define REP(i, a, b) for(int i = (a); i < (b); ++i) typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<bool> vb; typedef set<int> si; vi dfn, mi; vi stk; vb ist, vis; int cdfn = 1; vvi gp; vi gi; void tarjan(int c, vvi& adj) { assert(!vis[c]); mi[c] = dfn[c] = cdfn++; stk.push_back(c); assert(!ist[c]); ist[c] = true; vis[c] = true; for(int i : adj[c]) { if(!vis[i]) { tarjan(i, adj); } else if(ist[i]) { mi[c] = min(mi[c], dfn[i]); } } if(mi[c] == dfn[c]){ gp.emplace_back(); int cur; do{ cur = stk.back(); gi[cur] = (int) gp.size() - 1; stk.pop_back(); ist[cur] = false; gp.back().push_back(cur); } while(cur != c); } } 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(), m = u.size(); int k = 1; forR(i, m) k = max(k, c[i] + 1); forR(i, n) k = max(k, r[i] + 1); int N = n * k; vvi adj(N); // room i, key j -> i * k + j forR(i, n) forR(j, k) if(j != r[i]) adj[i * k + j].push_back(i * k + r[i]); forR(i, m) { adj[u[i] * k + c[i]].push_back(v[i] * k + c[i]); adj[v[i] * k + c[i]].push_back(u[i] * k + c[i]); } dfn.resize(N); mi.resize(N); ist.resize(N); vis.resize(N); gi.resize(N); forR(i, N) if(!vis[i]){ assert(stk.empty()); tarjan(i, adj); } forR(i, N) assert(vis[i]); // cerr << gp.size() << '\n'; // forR(i, N) cerr << gi[i] << ' '; // cerr << '\n'; vi gpt(gp.size()); forR(i, n) gpt[gi[i * k + r[i]]] += 1; vector<si> gAdj(gp.size()); forR(i, N) for(int j : adj[i]) if(gi[j] != gi[i]) gAdj[gi[i]].insert(gi[j]); forR(i, gp.size()) { for(int j : gAdj[i]) gpt[i] += gpt[j]; } vi cnt(n); forR(i, n) cnt[i] = gpt[gi[i * k + r[i]]]; int mi = cnt[0]; forR(i, n) mi = min(mi, cnt[i]); vi ans(n); forR(i, n) ans[i] = cnt[i] == mi ? 1 : 0; 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:3:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define forR(i, x) for(int i = 0; i < (x); ++i)
      |                                     ^
keys.cpp:69:2: note: in expansion of macro 'forR'
   69 |  forR(i, gp.size()) {
      |  ^~~~
#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...