이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
#define pii pair<int, int>
using namespace std;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e5 + 5;
int n, m, key_in[N], is_key[N], avail[N];
int finished[N], sol[N];
vector<pii> S[N];
vector<int> list_node[N], list_key, Q;
void solve(int u) {
for(int v : list_key) {
list_node[v].clear();
}
for(int v : Q) {
is_key[key_in[v]] = 0;
avail[v] = 0;
}
list_key.clear();
Q.clear();
int cnt = 1;
avail[u] = 1;
Q.push_back(u);
REP(i, 0, Q.size()) {
u = Q[i];
if (!is_key[key_in[u]]) {
is_key[key_in[u]] = 1;
for(int v : list_node[key_in[u]]) if (!avail[v]) {
if (finished[v]) return;
++cnt;
avail[v] = 1;
Q.push_back(v);
}
list_node[key_in[u]].clear();
}
for(auto [v, type] : S[u]) if (!avail[v]) {
if (is_key[type]) {
if (finished[v]) return;
++cnt;
avail[v] = 1;
Q.push_back(v);
}
else {
list_key.push_back(type);
list_node[type].push_back(v);
}
}
}
for(int v : Q) sol[v] = min(sol[v], cnt);
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
n = r.size();
m = u.size();
REP(i, 0, n) key_in[i] = r[i];
REP(i, 0, m) {
S[u[i]].emplace_back(v[i], c[i]);
S[v[i]].emplace_back(u[i], c[i]);
}
int mini = n;
vector<int> tmp;
REP(i, 0, n) REP(j, 0, S[i].size()) tmp.push_back(i);
shuffle(tmp.begin(), tmp.end(), rd);
REP(i, 0, n) sol[i] = 1e6;
for(int i : tmp) if (!finished[i]) {
solve(i);
finished[i] = true;
mini = min(mini, sol[i]);
}
vector<int> ans(n, 0);
REP(i, 0, n) ans[i] = (mini == sol[i]);
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
keys.cpp: In function 'void solve(int)':
keys.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
| ^
keys.cpp:29:5: note: in expansion of macro 'REP'
29 | REP(i, 0, Q.size()) {
| ^~~
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:3:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
| ^
keys.cpp:69:18: note: in expansion of macro 'REP'
69 | REP(i, 0, n) REP(j, 0, S[i].size()) tmp.push_back(i);
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |