Submission #1290731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290731		lucasdmy	Split the Attractions (IOI19_split)	C++20	40 / 100	63 ms	18364 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10, MAXM=2e5+10;
vector<int>v[MAXN], marc(MAXN), pai(MAXN);
int m1, m2, aux=-1;
bool ok;
int dfs(int x, int n){
    marc[x]=1;
    int subsize=1;
    for(int k=0;k<v[x].size();k++){
        if(marc[v[x][k]]==0){
            subsize+=dfs(v[x][k], n);
            pai[v[x][k]]=x;
        }
    }
    if(subsize>=m1 and n-subsize>=m2){
        aux=x;
        ok=true;
    }else if(subsize>=m2 and n-subsize>=m1){
        aux=x;
        ok=false;
    }
    return subsize;
}
vector<int>ord1, marc1(MAXN);
void ans1(int x){
    marc1[x]=1;
    ord1.push_back(x);
    for(int k=0;k<v[x].size();k++){
        if(marc1[v[x][k]]==0 and v[x][k]!=pai[aux]){
            ans1(v[x][k]);
        }
    }
}
vector<int>ord2, marc2(MAXN);
void ans2(int x){
    marc2[x]=1;
    ord2.push_back(x);
    for(int k=0;k<v[x].size();k++){
        if(marc2[v[x][k]]==0 and v[x][k]!=aux){
            ans2(v[x][k]);
        }
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int>n1, vector<int>n2){
    int m=n1.size();
    vector<int>resp(n, 0);
    for(int k=0;k<m;k++){
        v[n1[k]].push_back(n2[k]);
        v[n2[k]].push_back(n1[k]);
    }
    m1=min({a, b, c});
    int rm1, rm2;
    if(m1==a){
        rm1=1;
        m2=min(b, c);
        if(m2==b){
            rm2=2;
        }else{
            rm2=3;
        }
    }else if(m1==b){
        rm1=2;
        m2=min(a, c);
        if(m2==a){
            rm2=1;
        }else{
            rm2=3;
        }
    }else{
        rm1=3;
        m2=min(a, b);
        if(m2==a){
            rm2=1;
        }else{
            rm2=2;
        }
    }
    dfs(0, n);
    if(aux==-1){
        return resp;
    }
    ans1(aux);
    ans2(pai[aux]);
    if(ok){
        for(int k=0;k<m1;k++){
            resp[ord1[k]]=rm1;
        }
        for(int k=0;k<m2;k++){
            resp[ord2[k]]=rm2;
        }
    }else{
        for(int k=0;k<m1;k++){
            resp[ord2[k]]=rm1;
        }
        for(int k=0;k<m2;k++){
            resp[ord1[k]]=rm2;
        }
    }
    for(int k=0;k<n;k++){
        if(resp[k]==0){
            resp[k]=6-rm1-rm2;
        }
    }
    return resp;
}
/*int main()
{
    int n, m, a, b, c;
    cin>>n>>m>>a>>b>>c;
    vector<int>n1(m), n2(m);
    for(int k=0;k<m;k++){
        cin>>n1[k];
    }
    for(int k=0;k<m;k++){
        cin>>n2[k];
    }
    vector<int>resp=find_split(n, a, b, c, n1, n2);
    for(int k=0;k<n;k++){
        cout<<resp[k]<<' ';
    }
    return 0;
}*/

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