Submission #294473

#	Time	Username	Problem	Language	Result	Execution time	Memory
294473		albertolg101	Split the Attractions (IOI19_split)	C++17	18 / 100	122 ms	15224 KiB

split

#include<bits/stdc++.h>
#include "split.h"

using namespace std;

vector<int> a_is_equal_to_one (int b, int c, int n, vector<vector<int>> &G)
{
    vector<bool> flag(n); 
    int cnt = 1;

    function<void(int)> dfs1 = [&]( int nod )
    {
        for(auto i: G[nod])
        {
            if( cnt == b ) 
                return ;

            if(flag[i])
                continue; 

            flag[i] = 1; 
            cnt++; 

            dfs1(i); 
        }
    } ;

    flag[0] = true; 
    dfs1(0); 

    bool a = false ; 
    vector<int> ans(n);

    for( int i = 0 ; i < n ; i++ )
    {
        if( flag[i] ) 
            ans[i] = 2 ; 
        
        else if( a )
            ans[i] = 3 ; 
        
        else
            ans[i] = 1, a = true; 
    }

    return ans ; 
}

vector<int> is_a_line (int a, int b, int c, int n, vector<vector<int>> &G)
{
    int root = 0;
    for( int i = 0 ; i < n ; i++ ) 
        if( G[i].size() == 1 ) 
            root = i ; 

    vector<int> ans(n);

    function<void(int, int)> dfs = [&](int nod, int lvl)
    {
        if( lvl <= a ) 
            ans[nod] = 1; 
        
        else if( lvl <= a + b ) 
            ans[nod] = 2 ;
        
        else 
            ans[nod] = 3 ; 

        for( auto target : G[nod] )
        {
            if( ans[target] == 0 )
                dfs( target , lvl + 1 ) ; 
        }
    } ;

    dfs(root, 1);

    return ans;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    
    vector<vector<int>> G(n + 1);
    int m = p.size(), degree = 0; 

    for(int i = 0; i < m; i++)
    {
        G[p[i]].push_back(q[i]);
        G[q[i]].push_back(p[i]);

        degree = max({ degree, (int)G[p[i]].size() , (int)G[q[i]].size() });
    }

    if(a == 1) 
        return a_is_equal_to_one(b, c, n, G); 

    else 
        return is_a_line(a, b, c, n, G);

}

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