Submission #880520

#	Time	Username	Problem	Language	Result	Execution time	Memory
880520		andrei_boaca	Split the Attractions (IOI19_split)	C++17	100 / 100	102 ms	28448 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> kids[100005],edges[100005];
vector<int> dsu[100005];
bool rebel[100005];
int comp[100005];
vector<pii> g;
vector<int> linie;
int par[100005];
bool use[100005];
vector<int> nodes;
int nr[100005];
int niv[100005],nivmin[100005];
int part[100005];
void dfs(int nod)
{
    nr[nod]=1;
    use[nod]=1;
    nivmin[nod]=niv[nod];
    for(int i:edges[nod])
    {
        if(i==par[nod])
            continue;
        if(!use[i])
        {
            niv[i]=niv[nod]+1;
            par[i]=nod;
            dfs(i);
            kids[nod].push_back(i);
            nr[nod]+=nr[i];
            nivmin[nod]=min(nivmin[nod],nivmin[i]);
        }
        else
            nivmin[nod]=min(nivmin[nod],niv[i]);
    }
}
bool valid(int nod)
{
    if(nr[nod]<take[ord[1]])
        return 0;
    for(int i:kids[nod])
        if(nr[i]>=take[ord[1]])
            return 0;
    return 1;
}
bool good(int lg1,int lg2)
{
    return min(lg1,lg2)>=take[ord[1]]&&max(lg1,lg2)>=take[ord[2]];
}
void put(int nod,int x)
{
    part[nod]=x;
    for(int i:kids[nod])
        if(part[i]==0)
            put(i,x);
}
void build(int nod,int x)
{
    nodes.push_back(nod);
    use[nod]=1;
    for(int i:edges[nod])
        if(part[i]==x&&!use[i])
            build(i,x);
}
void go(int nod,int x)
{
    part[nod]=x;
    for(int i:edges[nod])
        if(part[i]==0)
            go(i,x);
}
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;
    }
    for(int i=0;i<p.size();i++)
    {
        int a,b;
        a=p[i];
        b=q[i];
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    niv[0]=1;
    dfs(0);
    for(int v=0;v<n;v++)
        if(valid(v))
        {
            vector<int> rebeli;
            int lg1=nr[v],lg2=n-nr[v];
            for(int i=0;i<kids[v].size();i++)
            {
                int u=kids[v][i];
                rebel[u]=0;
                if(nivmin[u]<niv[v]&&lg1-nr[u]>=take[ord[1]])
                {
                    lg1-=nr[u];
                    rebeli.push_back(u);
                    rebel[u]=1;
                    lg2+=nr[u];
                }
            }
            if(good(lg1,lg2))
            {
                for(int i=0;i<n;i++)
                    use[i]=0;
                part[v]=1;
                for(int i:kids[v])
                    if(!rebel[i])
                        put(i,1);
                int z=0;
                for(int i=0;i<n;i++)
                    if(part[i]==0)
                    {
                        z=i;
                        break;
                    }
                int c1=ord[1];
                int c2=ord[2];
                if(lg1>lg2)
                {
                    swap(c1,c2);
                }
                go(z,2);
                nodes.clear();
                build(v,1);
                for(int i=0;i<take[c1];i++)
                    sol[nodes[i]]=c1;
                nodes.clear();
                int r=-1;
                for(int i=0;i<n;i++)
                    if(part[i]==2)
                        {
                            r=i;
                            break;
                        }
                build(r,2);
                for(int i=0;i<take[c2];i++)
                    sol[nodes[i]]=c2;
                for(int i=0;i<n;i++)
                    if(sol[i]==0)
                        sol[i]=ord[3];
                return sol;
            }
        }
    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:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i=0;i<p.size();i++)
      |                 ~^~~~~~~~~
split.cpp:118:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |             for(int i=0;i<kids[v].size();i++)
      |                         ~^~~~~~~~~~~~~~~

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