Submission #1190102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190102		alexdd	Split the Attractions (IOI19_split)	C++20	7 / 100	41 ms	15176 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> con[200005];
int cntv;
vector<int> visited;
void dfs(int nod, int b, int val)
{
    if(cntv==b)
        return;
    visited[nod] = val;
    cntv++;
    for(int adj:con[nod])
        if(!visited[adj])
            dfs(adj,b,val);
}
std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q)
{
    visited.resize(n,0);
    for(int i=0;i<p.size();i++)
    {
        con[p[i]].push_back(q[i]);
        con[q[i]].push_back(p[i]);
    }
    int cntcap=0;
    for(int cap=0;cap<n;cap++)
    {
        if(con[cap].size() == 1)
        {
            cntcap++;
            if(cntcap==1)
            {
                cntv=0;
                dfs(cap,a,1);
            }
            else
            {
                cntv=0;
                dfs(cap,b,2);
            }
        }
    }
    if(cntcap==0)
    {
        for(int cap=0;cap<n;cap++)
        {
            if(visited[cap]==0 && cntcap<2)
            {
                cntcap++;
                if(cntcap==1)
                {
                    cntv=0;
                    dfs(cap,a,1);
                }
                else
                {
                    cntv=0;
                    dfs(cap,b,2);
                }
            }
        }
    }
    assert(cntcap==2);
    for(int i=0;i<n;i++)
        if(visited[i]==0)
            visited[i]=3;
    return visited;
}

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