Submission #1290810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290810		lambd47	Split the Attractions (IOI19_split)	C++20	100 / 100	147 ms	19628 KiB

split

#include<bits/stdc++.h>
#include "split.h"
using namespace std;

#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()

const int MX=1e5+7;
vector<pair<int,int>> adj[MX];//onde vai e tipo
int tam[MX];
int n;

int dfstam(int node){
    tam[node]=1;
    L(i,0,sz(adj[node])-1){
        if(tam[adj[node][i].first]==0){
            adj[node][i].second=1;
            L(j,0,sz(adj[adj[node][i].first])-1){
                if(adj[adj[node][i].first][j].first==node)adj[adj[node][i].first][j].second=1;
            }
            tam[node]+=dfstam(adj[node][i].first);
        }
    }
    return tam[node];
}
int dfstam2(int node,int pai){
    tam[node]=1;
    for(auto [a,w]:adj[node]){
        if(w==0 || pai==a)continue;
        tam[node]+=dfstam2(a,node);
    }
    return tam[node];
}
int cen(int node,int pai){
    for(auto [a,w]:adj[node]){
        if(w==0 || a==pai)continue;
        if(tam[a]*2>n)return cen(a,node);
    }
    return node;
}
int rep[MX];
void findrep(int node,int pai,int r){
    rep[node]=r;
    for(auto [a,w]:adj[node]){
        if(w==0 || a==pai)continue;
        findrep(a,node,r);
    }
}

int c;
vector<int> ultradj[MX];
vector<int> resp;
void superliga(int node, int pai){
    for(auto [a,w]:adj[node]){
        if(a==pai)continue;
        if(w==0  && a!=c){
            if(rep[node]==rep[a])continue;
            ultradj[rep[node]].push_back(rep[a]);
            ultradj[rep[a]].push_back(rep[node]);
        }
        if(w==1){
            superliga(a,node);
        }
    }
}
void pintasub(int node, int pai,int cor){
    resp[node]=cor;
    for(auto [a,w]:adj[node]){
        if(w==0 || a==pai)continue;
        pintasub(a,node,cor);
    }
    return;
}

void pintoQnt(int node, int pai, int cor, int qnt){
    resp[node]=cor;
    qnt--;
    if(qnt<=0)return;
    for(auto [a,w]:adj[node]){
        if(w==0 || a==pai)continue;
        pintoQnt(a,node,cor,qnt);
        qnt-=tam[a];
        if(qnt<=0)return;
    }
    return;
}
int ultratam[MX];
int ultradfs(int node){
    ultratam[node]=tam[node];
    for(auto a:ultradj[node]){
        if(ultratam[a]==0)ultratam[node]+=ultradfs(a);
    }
    return ultratam[node];
}

void ultramarca(int node,int cor, int& qnt){
    if(qnt==0)return;
    if(tam[node]<=qnt){
        qnt-=tam[node];
        pintasub(node,c,cor);
    }
    else{
        pintoQnt(node,c,cor,qnt);
        qnt=0;
    }
    if(qnt==0)return;
    for(auto a:ultradj[node]){
        if(resp[a]!=0)continue;
        ultramarca(a,cor,qnt);
    }
}


vector<int> find_split(int nn, int aa, int bb, int cc, vector<int> p, vector<int> q) {
    n=nn;
    resp.resize(n);
    L(i,0,sz(p)-1){
        adj[p[i]].push_back({q[i],0});
        adj[q[i]].push_back({p[i],0});
    }
    dfstam(0);
    c=cen(0,0);
    L(i,0,n-1){
        tam[i]=0;
     //   L(j,0,sz(adj[i])-1){
     //       adj[i][j].second=0;
     //   }
    }
    dfstam2(c,c);
    for(auto [a,w]:adj[c]){
        if(w==0)continue;
        findrep(a,c,a);
    }
    vector<int> cor(3);iota(all(cor),1);
    int preciso[3]={aa,bb,cc};
    sort(all(cor),[&](int i, int j){
            return preciso[i-1]<preciso[j-1];
            });
    sort(preciso,preciso+3);//ver se eh +2

    for(auto [a,w]:adj[c]){
        if(w==0)continue;
        superliga(a,c);
    }

    for(auto [a,w]:adj[c]){
        if(w==0)continue;
        if(sz(ultradj[a])==0)continue;
        sort(all(ultradj[a]));
        ultradj[a].erase(unique(all(ultradj[a])),ultradj[a].end());
    }
   vector<int> vizc;
    for(auto [a,w]:adj[c]){
        if(w==0)continue;
        vizc.push_back(a);
    }

    for(auto a:vizc){
        if(ultratam[a]!=0)continue;
        ultradfs(a);
        if(ultratam[a]>=preciso[0]){//yayyy deu certo
            ultramarca(a,cor[0],preciso[0]);
            resp[c]=cor[1];
            preciso[1]--;
            for(auto x:vizc){
                if(preciso[1]==0)continue;
                if(resp[x]!=0)continue;
                if(tam[x]<=preciso[1]){
                    preciso[1]-=tam[x];
                    pintasub(x,c,cor[1]);
                }
                else{
                    pintoQnt(x,c,cor[1],preciso[1]);
                    preciso[1]=0;
                }
            }
            L(i,0,n-1)if(resp[i]==0)resp[i]=cor[2];
            return resp;
        }
    }
    return resp;









}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 24 / 24
• Subtask 5: 36 / 36