Submission #879163

#	Time	Username	Problem	Language	Result	Execution time	Memory
879163		andrei_boaca	Split the Attractions (IOI19_split)	C++17	0 / 100	5 ms	11156 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];
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);
        }
}
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++)
    {
        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++)
            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;
    }
    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:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0;i<p.size();i++)
      |                 ~^~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from split.cpp:2:
split.cpp:83:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |         assert(linie.size()==n);
      |                ~~~~~~~~~~~~^~~

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