Submission #879166

#	Time	Username	Problem	Language	Result	Execution time	Memory
879166		andrei_boaca	Split the Attractions (IOI19_split)	C++17	18 / 100	85 ms	25032 KiB

split

#include "split.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef pair<int,int> pii;
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];
vector<int> dsu[100005];
int comp[100005];
vector<pii> g;
vector<int> linie;
int par[100005];
bool use[100005];
vector<int> nodes;
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);
}
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];
        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;
    }
    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:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<p.size();i++)
      |                 ~^~~~~~~~~
split.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for(int i=0;i<nodes.size();i++)
      |                     ~^~~~~~~~~~~~~

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