이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define F first
#define S second
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define in insert
#define sz(s) (int)s.size()
// #define int ll
#define ppb pop_back
#define mem(a,i) memset(a,i,sizeof(a))
using namespace std;
const int MAX=3e5+15;
const int inf=1e9;
const int mod=1e9+7;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
vector<pii> g[MAX];
int n,m;
int tov[MAX];
set<int> st[MAX];
vector<int> ver[MAX];
int ban[MAX];
bool MR[MAX];
struct DSU{
int f[MAX];
int s[MAX];
void init(int n){
for(int i=1;i<=n;i++)f[i]=i,s[i]=1;
}
int get(int v){
return (f[v]==v?v:f[v]=get(f[v]));
}
void unite(int u,int v){
u=get(u);
v=get(v);
f[v]=u;
s[u]+=s[v];
}
}D,D1;
void mrg(int a,int b){
if(sz(st[a])<sz(st[b]))swap(st[a],st[b]);
for(int x:st[b])st[a].in(x);
st[b].clear();
if(sz(ver[a])<sz(ver[b])){
swap(ver[a],ver[b]);
}
for(int x:ver[b])ver[a].pb(x);
ver[b].clear();
}
vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c){
n=sz(r);
m=sz(u);
for(int i=0;i<m;i++){
u[i]++;
v[i]++;
g[u[i]].pb({v[i],c[i]});
g[v[i]].pb({u[i],c[i]});
}
D.init(n);
D1.init(n);
for(int i=1;i<=n;i++){
ver[i].pb(i);
st[i].in(r[i-1]);
}
while(1){
mem(MR,0);
int cnt=0;
// cerr<<1<<"\n";
for(int i=1;i<=n;i++){
if(ban[D.get(i)])continue;
if(!tov[D.get(i)]){
for(auto to:g[i]){
if(D.get(i)!=D.get(to.F)&&st[D.get(i)].count(to.S)){
if(ban[D.get(to.F)]){
ban[D.get(i)]=2;
break;
}
tov[D.get(i)]=D.get(to.F);
cnt++;
if(D1.get(i)==D1.get(to.F)){
tov[D.get(i)]=0;
MR[D.get(i)]=1;
{
int V=D.get(to.F);
while(D.get(V)!=D.get(i)){
mrg(D.get(i),V);
D.unite(i,V);
int TO=D.get(tov[V]);
tov[V]=0;
V=TO;
}
}
}
else{
D1.unite(i,to.F);
break;
}
}
}
}
}
for(int i=1;i<=n;i++){
if(ban[D.get(i)])continue;
if(tov[D.get(i)]==0&&!MR[D.get(i)]){
// cout<<D.get(i)<<"\n";
ban[D.get(i)]=1;
}
}
if(!cnt)break;
}
// return vector<int>(n,0);
int ans=inf;
for(int i=1;i<=n;i++){
if(D.get(i)==i){
cout<<ban[i]<<" ";
if(ban[i]==1){
ans=min(ans,D.s[i]);
}
}
}
// cout<<"\n";
// cout<<ans<<"\n";
vector<int> res(n,0);
for(int i=1;i<=n;i++){
if(ban[i]==1&&D.get(i)==i&&D.s[i]==ans){
for(auto v:ver[i]){
res[v-1]=1;
}
// cout<<"!! "<<i<<" "<<D.s[i]<<"\n";
}
}
return res;
}
# | 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... |