Submission #879185

#	Time	Username	Problem	Language	Result	Execution time	Memory
879185		andrei_boaca	Split the Attractions (IOI19_split)	C++17	40 / 100	485 ms	29984 KiB

split

#include "split.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("fast-math")
//#pragma GCC optimize ("unroll-loops")
using namespace std;
typedef pair<int,int> pii;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int n,m;
int take[5],ord[5];
vector<int> sol;
bool byval(int a,int b)
{
    return take[a]<take[b];
}
vector<int> muchii[100005],edges[100005];
vector<int> dsu[100005];
int comp[100005];
vector<pii> g;
vector<int> linie;
int par[100005];
bool use[100005];
vector<int> nodes;
int nr[100005];
void dsu_merge(int c1,int c2)
{
    if(dsu[c1].size()<dsu[c2].size())
        swap(c1,c2);
    for(int i:dsu[c2])
    {
        comp[i]=c1;
        dsu[c1].push_back(i);
    }
    dsu[c2].clear();
}
void dfslin(int nod)
{
    linie.push_back(nod);
    for(int i:muchii[nod])
        if(i!=par[nod])
        {
            par[i]=nod;
            dfslin(i);
        }
}
void dfsmake(int nod)
{
    nodes.push_back(nod);
    use[nod]=1;
    for(int i:muchii[nod])
        if(!use[i])
            dfsmake(i);
}
void dfs(int nod)
{
    nr[nod]=1;
    for(int i:muchii[nod])
        if(i!=par[nod])
        {
            par[i]=nod;
            dfs(i);
            nr[nod]+=nr[i];
        }
}
int root=0;
void make(int nod)
{
    use[nod]=1;
    for(int i:edges[nod])
        if(!use[i])
        {
            muchii[i].push_back(nod);
            muchii[nod].push_back(i);
            make(i);
        }
}
void build()
{
    for(int i=0;i<n;i++)
    {
        use[i]=0;
        muchii[i].clear();
        muchii[i].shrink_to_fit();
        nr[i]=0;
        par[i]=-1;
    }
    make(root);
    for(int i=0;i<n;i++)
        use[i]=0;
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q)
{
    n=N;
    take[1]=A;
    take[2]=B;
    take[3]=C;
    ord[1]=1;
    ord[2]=2;
    ord[3]=3;
    sort(ord+1,ord+4,byval);
    sol.resize(n);
    m=p.size();
    for(int i=0;i<n;i++)
    {
        par[i]=-1;
        comp[i]=i+1;
        dsu[i+1].push_back(i);
    }
    for(int i=0;i<p.size();i++)
    {
        int a=p[i];
        int b=q[i];
        edges[a].push_back(b);
        edges[b].push_back(a);
        g.push_back({a,b});
        if(comp[a]!=comp[b])
        {
            muchii[a].push_back(b);
            muchii[b].push_back(a);
            dsu_merge(comp[a],comp[b]);
        }
    }
    bool sub1=1;
    for(int i=0;i<n;i++)
        if(muchii[i].size()>2)
            sub1=0;
    if(sub1)
    {
        int root=0;
        for(int i=0;i<n;i++)
        {
            assert(muchii[i].size()>=1);
            if(muchii[i].size()==1)
            {
                root=i;
                break;
            }
        }
        dfslin(root);
        //assert(linie.size()==n);
        for(int i=0;i<n;i++)
        {
            if(i<A)
                sol[linie[i]]=1;
            else if(i<A+B)
                sol[linie[i]]=2;
            else
                sol[linie[i]]=3;
        }
        return sol;
    }
    if(A==1)
    {
        int who=0;
        for(int i=0;i<n;i++)
            if(muchii[i].size()==1)
            {
                who=i;
                break;
            }
        use[who]=1;
        sol[who]=1;
        dfsmake(muchii[who][0]);
        for(int i=0;i<nodes.size();i++)
            {
                if(i<B)
                    sol[nodes[i]]=2;
                else
                    sol[nodes[i]]=3;
            }
        return sol;
    }
    dfs(0);
    int x=-1,y=-1;
    for(int i=1;i<n;i++)
    {
        if(min(nr[i],n-nr[i])>=take[ord[1]]&&max(nr[i],n-nr[i])>=take[ord[2]])
        {
            x=i;
            y=par[i];
        }
    }
    if(x==-1)
    {
        bool found=0;
        if(n<=5000)
        {
            for(int r=0;r<n&&!found;r++)
            {
                root=r;
                build();
                dfs(root);
                for(int i=0;i<n&&!found;i++)
                    if(i!=root)
                        if(min(nr[i],n-nr[i])>=take[ord[1]]&&max(nr[i],n-nr[i])>=take[ord[2]])
                        {
                            x=i;
                            y=par[i];
                            found=1;
                        }
            }
        }
        if(!found)
            return sol;
    }
    if(nr[x]>n-nr[x])
        swap(x,y);
    use[x]=1;
    use[y]=1;
    nodes.clear();
    dfsmake(x);
    sol[x]=ord[1];
    for(int i=1;i<nodes.size();i++)
    {
        if(i<=take[ord[1]]-1)
            sol[nodes[i]]=ord[1];
        else
            sol[nodes[i]]=ord[3];
    }

    nodes.clear();
    dfsmake(y);
    sol[y]=ord[2];
    for(int i=1;i<nodes.size();i++)
    {
        if(i<=take[ord[2]]-1)
            sol[nodes[i]]=ord[2];
        else
            sol[nodes[i]]=ord[3];
    }
    return sol;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int i=0;i<p.size();i++)
      |                 ~^~~~~~~~~
split.cpp:165:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         for(int i=0;i<nodes.size();i++)
      |                     ~^~~~~~~~~~~~~
split.cpp:214:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |     for(int i=1;i<nodes.size();i++)
      |                 ~^~~~~~~~~~~~~
split.cpp:225:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |     for(int i=1;i<nodes.size();i++)
      |                 ~^~~~~~~~~~~~~

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