| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1094567 | azberjibiou | Keys (IOI21_keys) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=300050;
const int mxM=10000;
const int mxK=60;
const ll INF=1e18;
struct uf{
int par[mxN];
set <pii> noE[mxN];
set <int> keys[mxN];
vector <int> okE[mxN];
int pnt[mxN];
int fp(int a){return par[a]==a ? a : par[a]=fp(par[a]);}
void mrg1(int a, int b){
int p=fp(a), q=fp(b);
if(p==q) return;
int szp=keys[p].size()+noE[p].size(), szq=keys[q].size()+noE[q].size();
if(szp>szq) swap(p, q);
for(int x : keys[p]){
while(true){
auto it=noE[q].lower_bound(pii(x, 0));
if(it!=noE[q].end() && it->fi==x){
okE[q].push_back(it->se);
noE[q].erase(it);
}
else break;
}
}
for(auto [x, y] : noE[p]){
if(keys[q].find(x)!=keys[q].end()) okE[q].push_back(y);
else noE[q].insert(pii(x, y));
}
if(okE[p].size()>okE[q].size()) swap(okE[p], okE[q]);
for(int x : okE[p]) okE[q].push_back(x);
par[p]=q;
}
void mrg2(int a, int b){par[fp(a)]=fp(b);}
};
int N, M;
int R[mxN];
vector<pii> v[mxN];
uf U1, U2;
void input(){
cin >> N >> M;
for(int i=0;i<N;i++) cin >> R[i];
for(int i=0;i<M;i++){
int a, b, c;
cin >> a >> b >> c;
v[a].emplace_back(b, c);
v[b].emplace_back(a, c);
}
}
void set_uf(){
for(int i=0;i<N;i++) U1.par[i]=i, U1.pnt[i]=-1;
for(int i=0;i<N;i++) U1.keys[i].insert(R[i]);
for(int i=0;i<N;i++){
for(auto [x, y] : v[i]){
if(R[i]==y) U1.okE[i].push_back(x);
else U1.noE[i].insert(pii(y, x));
}
}
for(int i=0;i<N;i++) U2.par[i]=i;
}
void make_graph(){
for(int i=0;i<N;i++){
while(true){
int now=U1.fp(i);
if(U1.okE[now].empty()){
U1.pnt[now]=-1;
break;
}
int nxt=U1.okE[now].back();
nxt=U1.fp(nxt);
U1.okE[now].pop_back();
if(nxt==now) continue;
if(U2.fp(nxt)!=U2.fp(now)){
U1.okE[now].push_back(nxt);
U1.pnt[now]=nxt;
U2.mrg2(nxt, now);
//printf("%d -> %d\n", now, nxt);
break;
}
vector <int> mrgv;
while(nxt!=now){
mrgv.push_back(nxt);
nxt=U1.fp(U1.pnt[nxt]);
//printf("mrg(%d %d)\n", nxt, now);
}
for(int x : mrgv) U1.mrg1(nxt, x);
}
}
//for(int i=0;i<N;i++) printf("par[%d]=%d %d\n", i, U1.fp(i), U2.fp(i));
//for(int i=0;i<N;i++) printf("E[%d]=%d\n", i, U1.okE[i].empty());
}
vector <int> ans;
int cnt[mxN];
int sz[mxN];
void count(){
for(int i=0;i<N;i++) sz[U1.fp(i)]++;
for(int i=0;i<N;i++){
int p=U1.fp(i);
if(U1.pnt[p]==-1) cnt[i]=sz[p];
else cnt[i]=999999;
}
int mini=999999;
for(int i=0;i<N;i++) mini=min(mini, cnt[i]);
ans.resize(N);
for(int i=0;i<N;i++) ans[i]=(cnt[i]==mini);
}
vector<int> find_reachable(vector<int> r, vector<int> u1, vector<int> u2, vector<int> c) {
N=r.size(), M=u1.size();
for(int i=0;i<N;i++) R[i]=r[i];
for(int i=0;i<M;i++){
int a=u1[i], b=u2[i], t=c[i];
v[a].emplace_back(b, t);
v[b].emplace_back(a, t);
}
set_uf();
make_graph();
count();
return ans;
}
int main(){
gibon
input();
set_uf();
make_graph();
count();
for(int x : ans) printf("%d ", x);
}