| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1060587 | jamjanek | 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.
#include<bits/stdc++.h>
using namespace std;
int rozmiar[300010];
int father1[300010];
int father2[300010];
int ojciec[300010];
int find1(int x){
if(father1[x]==x)return x;
return father1[x] = find1(father1[x]);
}
void union1(int a, int b){
a = find1(a);
b = find1(b);
if(a!=b)
father1[b] = a;
}
set<int>klucze[300010];
set<int>graf[300010];
set<pair<int,int>>zablokowane[300010];
int find2(int x){
if(father2[x]==x)return x;
return father2[x] = find2(father2[x]);
}
void union2(int a, int b){
a = find2(a);
b = find2(b);
if(rozmiar[a] < rozmiar[b])swap(a,b);
rozmiar[a]+=rozmiar[b];
father2[b] = a;
for(auto j: graf[b])
graf[a].insert(j);
for(auto j: klucze[b]){
if(klucze[a].find(j)!=klucze[a].end())continue;
klucze[a].insert(j);
auto pom = zablokowane[a].lower_bound({j,-1});
while((pom)!=zablokowane[a].end() && (*pom).first==j){
graf[a].insert((*pom).second);
zablokowane[a].erase(*pom);
pom = zablokowane[a].lower_bound({j, -1});
}
}
for(auto j: zablokowane[b]){
if(klucze[a].find(j.first)!=klucze[a].end())
graf[a].insert(j.second);
else
zablokowane[a].insert(j);
}
}
int main()
{
int n, m, a, b, c, i;
assert(scanf("%d%d", &n, &m));
for(i=0;i<n;i++){
assert(scanf("%d", &a));
father1[i] = i;
father2[i] = i;
rozmiar[i] = 1;
klucze[i].insert(a);
ojciec[i] = -1;
}
for(i=0;i<m;i++){
assert(scanf("%d%d%d", &a, &b, &c));
if(klucze[a].find(c)!=klucze[a].end())
graf[a].insert(b);
else
zablokowane[a].insert({c,b});
if(klucze[b].find(c)!=klucze[b].end())
graf[b].insert(a);
else
zablokowane[b].insert({c,a});
}
queue<int>kolejka;
for(i=0;i<n;i++){
if(graf[i].size()>0)
kolejka.push(i);
}
while(kolejka.size()){
int x = kolejka.front();
kolejka.pop();
x = find2(x);
ojciec[x] = find2(*(graf[x].begin()));
//printf("%d %d\n", x, ojciec[x]);
graf[x].erase(graf[x].begin());
if(find1(ojciec[x])!=find1(x)){
union1(x, ojciec[x]);
continue;
}
vector<int>pom;
int z = ojciec[x];
while(find2(z)!=find2(x)){
pom.push_back(z);
z = ojciec[z];
}
pom.push_back(z);
for(i=1;i<(int)pom.size();i++){
union2(pom[i-1], pom[i]);
}
x = find2(x);
//printf("po zcaleniu %d\n", x);
ojciec[x] = -1;
while(!graf[x].empty() && find2(*graf[x].begin())==x){
graf[x].erase(graf[x].begin());
}
if(graf[x].size()>0)
kolejka.push(x);
}
int wynik = n;
for(i=0;i<n;i++)
if(ojciec[find2(i)]==-1)
wynik = min(wynik, rozmiar[find2(i)]);
for(i=0;i<n;i++)
printf("%d ", (ojciec[find2(i)]==-1 && wynik==rozmiar[find2(i)]));
// for(i=0;i<n;i++)
// printf("%d ", ojciec[find2(i)]);
// for(i=0;i<n;i++)
// printf("%d ", rozmiar[find2(i)]);
}