Submission #143909

#	Time	Username	Problem	Language	Result	Execution time	Memory
143909		Bodo171	Split the Attractions (IOI19_split)	C++14	40 / 100	231 ms	19880 KiB

split

#include "split.h"
#include <iostream>
#include <algorithm>
using namespace std;
const int nmax=100005;
vector<int> res;
vector<int> ad[nmax],v[nmax];
pair<int,int> C[3];
int viz[nmax],q[nmax],w[nmax],tt[nmax];
int i,n;
void sterge(int A,int B)
{
    for(int it=0;it<2;it++)
    {
        for(int i=0;i<v[A].size();i++)
            if(v[A][i]==B)
        {
            swap(v[A][i],v[A].back());
            v[A].pop_back();
        }
        swap(A,B);
    }
}
void et(int x,int cate,int col)
{
    int p,u;
    for(i=0;i<n;i++)
        viz[i]=0;
    viz[x]=1;
    q[u=1]=x;
    for(p=1;p<=u;p++)
    {
        x=q[p];
        for(int i=0;i<v[x].size();i++)
            if(!viz[v[x][i]])
        {
            q[++u]=v[x][i];
            viz[v[x][i]]=1;
        }
    }
    for(i=1;i<=cate;i++)
        res[q[i]]=col;
}
bool gasit;
void solve(int x)
{
    w[x]=1;
    for(int i=0;i<v[x].size();i++)
        if((!w[v[x][i]]))
    {
        tt[v[x][i]]=x;
        solve(v[x][i]);
        w[x]+=w[v[x][i]];
    }
    if(!gasit)
    {
        if(w[x]>=C[0].first&&n-w[x]>=C[1].first)
        {
            sterge(x,tt[x]);
            et(x,C[0].first,C[0].second);
            et(tt[x],C[1].first,C[1].second);
            gasit=1;
        }
        else
        {
            if(w[x]>=C[1].first&&n-w[x]>=C[0].first)
            {
                sterge(x,tt[x]);
                et(x,C[1].first,C[1].second);
                et(tt[x],C[0].first,C[0].second);
                gasit=1;
            }
        }
    }
}
void dfs(int x)
{
    for(int i=0;i<ad[x].size();i++)
        if(tt[ad[x][i]]==-1)
    {
        tt[ad[x][i]]=x;
        dfs(ad[x][i]);
    }
}
void get_spanning(int x)
{
    for(i=0;i<n;i++)
        tt[i]=-1;
    tt[x]=x;
    dfs(x);
    for(i=0;i<n;i++)
        v[i].clear();
    for(i=0;i<n;i++)
        if(tt[i]!=i)
    {
        v[tt[i]].push_back(i);
        v[i].push_back(tt[i]);
    }
    solve(0);
}
vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
    n=nn;
    for(i=0;i<p.size();i++)
    {
        ad[p[i]].push_back(q[i]);
        ad[q[i]].push_back(p[i]);
    }
    res.resize(n);
    for(i=0;i<n;i++)
        res[i]=0;
    pair<int,int> v[3];
    C[0]={a,1};
    C[1]={b,2};
    C[2]={c,3};
    sort(C,C+3);
    get_spanning(0);
    if(gasit)
    {
        int oth=(C[0].second^C[1].second);
        for(i=0; i<n; i++)
            if(!res[i])
                res[i]=oth;
    }
	return res;
}

Compilation message (stderr)

split.cpp: In function 'void sterge(int, int)':
split.cpp:15:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v[A].size();i++)
                     ~^~~~~~~~~~~~
split.cpp: In function 'void et(int, int, int)':
split.cpp:34:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v[x].size();i++)
                     ~^~~~~~~~~~~~
split.cpp: In function 'void solve(int)':
split.cpp:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
split.cpp: In function 'void dfs(int)':
split.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ad[x].size();i++)
                 ~^~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:103:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<p.size();i++)
             ~^~~~~~~~~
split.cpp:111:19: warning: unused variable 'v' [-Wunused-variable]
     pair<int,int> v[3];
                   ^

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