| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1073415 | 2024-08-24T14:22:10 Z | Itamar | Distributing Candies (IOI21_candies) | C++17 | 0 ms | 0 KB |
using namespace std;
#include <vector>
#define vi vector<int>
#include <map>
#include<set>
#include<queue>
const int siz = 3e5+2;
int my[siz];
int fun[siz];
vi que[siz];
vi col[siz];
map<int,vi> locked[siz];
int fin[siz];
set<int> keys[siz];
set<int> s;
int n;
void kil(int c){
fin[c]=2;
if(s.find(c)!=s.end())s.erase(c);
}
void con(int a, int b){
a = my[a], b = my[b];
if(a==b)return;
if(fin[a]){
kil(b);
return;
}
if(fin[b]){
kil(a);
return;
}
if(col[a].size() > col[b].size())swap(a,b);
for(int k : keys[a]){
for(int l : locked[b][k]){
que[b].push_back(l);
}
locked[b][k].clear();
keys[b].insert(k);
}
for(auto[l,v] : locked[a]){
if(keys[b].find(l)!=keys[b].end()){
for(int i : v)que[b].push_back(i);
}else{
for(int i : v)locked[b][l].push_back(i);
}
}
for(int i : que[a])que[b].push_back(i);
if(s.find(a)!=s.end()){
s.erase(a);
s.insert(b);
}
for(int i : col[a]){
my[i]=b;
col[b].push_back(i);
}
}
int padf(int f){
f=my[f];
if(s.find(my[fun[f]]) == s.end() && fin[my[fun[f]]] == 0){
fun[f] = padf(my[fun[f]]);
return fun[f];
}else return f;
}
void iter(){
vi k,er;
vector<pair<int,int>> co;
vi popo;
for(int c : s){ // may be problematic because we kill stuff from s
while(que[c].size()){
int f = que[c].back();
f=my[f];
if(f == c){
que[c].pop_back();
continue;
}
if(fin[f]){
k.push_back(c);
fun[c]=c;
break;
}else if(s.find(f)!=s.end()){
fun[c]=f;
break;
}else{
f=padf(f);
int m = my[fun[f]];
if(fin[m]){
fun[c]=c;
k.push_back(c);
break;
}
if(m == c){
fun[c]=c;
popo.push_back(c);
co.push_back({f,c});
break;
}else{
fun[c]=m;
break;
}
}
}
if(que[c].empty()){
er.push_back(c);
fin[c]=1;
fun[c]=c;
continue;
}
}
map<int,int> deg;
queue<int> q;
for(int i : s)deg[my[fun[i]]]++;
for(int i : s)if(deg[i]==0)q.push(i);
while(!q.empty()){
int i = q.front();
int f = my[fun[i]];
q.pop();
// if(fin[fun[i]]){kil(i);continue;}
deg[f]--;
if(deg[f]==0)q.push(f);
}
vi erer;
for(int i : s){
if(deg[i])co.push_back({i,fun[i]});
else erer.push_back(i);
}
for(int p : popo)que[p].pop_back();
for(int e : er)s.erase(e);
for(int e : erer)s.erase(e);
for(int ki : k)kil(ki);
for(auto[a,b]:co)con(a,b);
}
vi find_reachable(vi R, vi U,vi V,vi C){
n = R.size();
for(int i = 0; i < n; i++)fun[i]=i;
for(int i = 0; i < n; i++){
my[i]=i;
col[i].push_back(i);
keys[i].insert(R[i]);
s.insert(i);
}
for(int i = 0; i < U.size(); i++){
int a = U[i], b = V[i];
if(*keys[a].begin() == C[i]){
que[a].push_back(b);
}else{
locked[a][C[i]].push_back(b);
}
if(*keys[b].begin() == C[i]){
que[b].push_back(a);
}else{
locked[b][C[i]].push_back(a);
}
}
while(s.size()){
iter();
}
vi ans(n);
int mini = 1e9;
for(int i = 0; i < n; i++){
if(fin[i]==1)mini = min(mini,(int)col[i].size());
}
for(int i =0 ; i< n; i++){
if(fin[i]==1){
if(col[i].size() == mini){
for(int j : col[i])ans[j]=1;
}
}
}
return ans;
}