제출 #879174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
879174		andrei_boaca	Split the Attractions (IOI19_split)	C++17	40 / 100	1411 ms	24520 KiB

split

#include "split.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
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];
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];
        }
}
void build()
{
    shuffle(g.begin(),g.end(),rng);
    for(int i=0;i<n;i++)
    {
        muchii[i].clear();
        muchii[i].shrink_to_fit();
    }
    for(int i=0;i<n;i++)
    {
        par[i]=-1;
        comp[i]=i+1;
        dsu[i+1].clear();
        dsu[i+1].shrink_to_fit();
        dsu[i+1].push_back(i);
    }
    for(int i=0;i<g.size();i++)
    {
        int a=g[i].first;
        int b=g[i].second;
        if(comp[a]!=comp[b])
        {
            muchii[a].push_back(b);
            muchii[b].push_back(a);
            dsu_merge(comp[a],comp[b]);
        }
    }
}
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;
    }
    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<=2500)
        {
            for(int t=1;t<=4000&&!found;t++)
            {
                build();
                dfs(0);
                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];
                        found=1;
                        break;
                    }
                }
            }
        }
        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;
}

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'void build()':
split.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0;i<g.size();i++)
      |                 ~^~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i=0;i<p.size();i++)
      |                 ~^~~~~~~~~
split.cpp:162:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |         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