이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
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) {
assert(iter < maxe(r) + 5);
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 {
assert(false);
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 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... |