이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 3e5+10;
set<int> heads;
struct DSU{
set<int> keys[mxn];
vector<pii> edges[mxn];
int dsu[mxn],sz[mxn];
DSU(){
iota(dsu,dsu+mxn,0);
fill(sz,sz+mxn,1);
}
int root(int k){
return k == dsu[k]?k:dsu[k] = root(dsu[k]);
}
void onion(int a,int b){
a = root(a),b = root(b);
if(a == b)return;
if(heads.find(b) != heads.end())heads.erase(b);
if(sz[a]<sz[b])swap(a,b);
dsu[b] = a;
sz[a] += sz[b];
if(edges[a].size()<edges[b].size())edges[a].swap(edges[b]);
if(keys[a].size()<keys[b].size())keys[a].swap(keys[b]);
for(auto &i:keys[b])keys[a].insert(i);
while(!edges[b].empty()){
auto now = edges[b].back();edges[b].pop_back();
if(root(now.fs) == a)continue;
edges[a].push_back(now);
}
return;
}
};
DSU dsu;
int N;
namespace SHRINK{
vector<int> paths[mxn];
bitset<mxn> done;
int idx[mxn],low[mxn];
vector<int> st;
int cnt = 0;
bool flag = false;
void dfs(int now){
idx[now] = low[now] = ++cnt;
st.push_back(now);
for(auto nxt:paths[now]){
if(done[nxt])continue;
if(!idx[nxt]){
dfs(nxt);
low[now] = min(low[now],low[nxt]);
}
else low[now] = min(low[now],idx[nxt]);
}
if(low[now] == idx[now]){
if(st.back() != now)flag = true;
while(st.back() != now){
dsu.onion(now,st.back());
done[st.back()] = true;
st.pop_back();
}
done[st.back()] = true;
st.pop_back();
}
return;
}
bool GO(){
cnt = 0;
flag = false;
for(auto &now:heads){
for(auto &[nxt,w]:dsu.edges[now]){
nxt = dsu.root(nxt);
if(nxt != now&&dsu.keys[now].find(w) != dsu.keys[now].end()){
paths[now].push_back(nxt);
}
}
}
for(auto &i:heads){
if(!done[i])dfs(i);
}
for(auto &i:heads){
done[i] = false;
idx[i] = low[i] = 0;
}
return flag;
}
}
namespace ANSWER{
bitset<mxn> leaf;
vector<int> GO(){
leaf.set();
int mn = 1e9;
for(auto &now:heads){
for(auto &[nxt,w]:dsu.edges[now]){
nxt = dsu.root(nxt);
if(nxt == now)continue;
if(dsu.keys[now].find(w) != dsu.keys[now].end())leaf[now] = false;
}
if(leaf[now])mn = min(mn,dsu.sz[now]);
}
vector<int> ans(N,0);
for(int i = 0;i<N;i++){
int now = dsu.root(i);
if(!leaf[now]||dsu.sz[now] != mn)ans[i] = false;
else ans[i] = true;
}
return ans;
}
}
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
N = r.size();
for(int i = 0;i<N;i++)heads.insert(i);
for(int i = 0;i<N;i++){
dsu.keys[i].insert(r[i]);
}
for(int i = 0;i<u.size();i++){
int a = u[i],b = v[i],tp = c[i];
dsu.edges[a].push_back(pii(b,tp));
dsu.edges[b].push_back(pii(a,tp));
}
int cnt = 0;
while(SHRINK::GO()){
cnt++;
}
assert(cnt<=30);
cerr<<cnt<<" epoches"<<endl;
return ANSWER::GO();
}
컴파일 시 표준 에러 (stderr) 메시지
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:129:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int i = 0;i<u.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... |