| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1066212 | epicci23 | 열쇠 (IOI21_keys) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int N = 3e5 + 5;
vector<int> v[N],comp[N];
set<array<int,2>> adj[N];
set<int> s[N];
bool vis[N],vis2[N],mark[N];
vector<int> cur,par(N,0);
void merge_info(int a,int b){
a=par[a],b=par[b];
if(a==b) return;
if(sz(comp[a])+sz(s[a])+sz(adj[a])+sz(v[a])
<sz(comp[b])+sz(s[b])+sz(adj[b])+sz(v[b])) swap(a,b);
mark[a]&=mark[b];
for(int x:v[b]) v[a].push_back(x);
for(int x:comp[b]){
comp[a].push_back(x);
par[x]=a;
}
for(array<int,2> x:adj[b]){
if(s[a].count(x[0])) v[a].push_back(x[1]);
else adj[a].insert(x);
}
for(int u:s[b]){
if(s[a].count(u)) continue;
s[a].insert(u);
auto it=adj[a].lower_bound({u,0});
while(it!=adj[a].end() && (*it).first==u){
v[a].push_back((*it).second);
adj[a].erase(*it);
it=adj[a].lower_bound({u,0});
}
}
adj[b].clear();
v[b].clear();
comp[b].clear();
s[b].clear();
}
void dfs(int c){
vis2[c]=vis[c]=1;
cur.push_back(c);
while(!v[par[c]].empty()){
int x=v[par[c]].back();
v[par[c]].pop_back();
if(vis[x] && !vis2[x]){
mark[par[c]]=0;
continue;
}
if(vis[x]==1){
while(!cur.empty() && par[cur.back()]!=par[x]){
merge_info(cur.back(),x);
cur.pop_back();
}
}
else{
dfs(x);
if(par[c]!=par[x]) mark[par[c]]=0;
}
}
if(!cur.empty() && cur.back()==c) cur.pop_back();
vis2[c]=0;
}
vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C){
int n=sz(R),m=sz(U);
iota(all(par),0);
for(int i=0;i<n;i++){
mark[i]=1;
comp[i].push_back(i);
s[i].insert(R[i]);
}
for(int i=0;i<m;i++){
int a=U[i],b=V[i],c=C[i];
if(s[a].count(c)) v[a].push_back(b);
else adj[a].insert({c,b});
if(s[b].count(c)) v[b].push_back(a);
else adj[b].insert({c,a});
}
for(int i=0;i<n;i++) if(!vis[i]) dfs(i);
int mini=100000007;
for(int i=0;i<n;i++) if(mark[par[i]]) mini=min(mini,sz(comp[par[i]]));
vector<int> ans(n,0);
for(int i=0;i<n;i++) if(mark[par[i]] && sz(comp[par[i]])==mini) ans[i]=1;
return ans;
}
/*void _(){
int n,m;
cin >> n >> m;
iota(all(par),0);
for(int i=0;i<n;i++) comp[i].push_back(i);
vector<int> col(n);
for(int i=0;i<n;i++) cin >> col[i];
for(int i=0;i<n;i++) s[i].insert(col[i]);
for(int i=0;i<m;i++){
int a,b,c;
cin >> a >> b >> c;
v[a][c].push_back(b);
v[b][c].push_back(a);
}
for(int i=0;i<n;i++) if(vis[i]==0) dfs(i);
int mini=100000007;
for(int i=0;i<n;i++){
if(mark[par[i]]) continue;
mini=min(mini,sz(comp[par[i]]));
}
vector<int> ans(n,0);
for(int i=0;i<n;i++) if(!mark[par[i]] && sz(comp[par[i]])==mini) ans[i]=1;
for(int i=0;i<n;i++) cout << ans[i] << " \n"[i==n-1];
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/