제출 #295979

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295979		albertolg101	Split the Attractions (IOI19_split)	C++17	40 / 100	1073 ms	19196 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> is_a_tree ( int a , int b , int c , int n , vector<vector<int>> &G )
{
    vector<int> size(n); 
    
    vector<int> ar = {a, b, c}, map;
    sort( ar.begin() , ar.end() );

    for( int i = 0 ; i <= 2 ; i++ ) 
    {
        if( ar[i] == a )
            map.push_back(1), a = -1;
        
        else if(ar[i] == b)
            map.push_back(2), b = -1; 
        
        else if(ar[i] == c )
            map.push_back(3), c = -1;
    }

    function<int(int, int)> dfs1 = [&]( int nod , int father )
    {
        size[nod] = 1 ; 

        for( auto target : G[nod] ) 
        {
            if( target == father ) 
                continue ;

            size[nod] += dfs1(target, nod); 
        }

        return size[nod]; 
    } ;

    dfs1(0, -1);

    function<pair<int, pair<int, int>>(int, int, int)> dfs2 = [&]( int nod , int father , int fatherSize )
    {
        pair<int, pair<int, int>> ans = {0, {nod, nod}}; 
        vector<pair<int, int>> child ;

        child.push_back({fatherSize, father});

        for( auto target : G[nod] )
        {
            if( target == father ) 
                continue ; 

            child.push_back({size[target], target});
            ans = max( ans , dfs2(target, nod, fatherSize + size[nod] - size[target] )); 
        }

        int Size = n - 1 ; 
        for( auto i : child )
            if( Size - i.first >= ar[1] )
                ans = max( ans , {i.first, {nod, i.second}} );  

        return ans ;
    };

    int cnt = 0 ; 
    vector<int> ans(n);
    
    function<void(int, int, int)> dfs3 = [&]( int nod , int father , int val )
    {
        ans[nod] = map[val] ; 
        cnt++; 

        if( cnt == ar[val] )
            return ; 

        for( auto target : G[nod] ) 
        {
            if( father == target )
                continue ; 

            dfs3(target, nod, val); 
            if( cnt == ar[val] ) 
                return ; 
        }
    };
    
    pair<int, pair<int, int>> dfsAns = dfs2(0, 0, 0); 

    if( dfsAns.first >= ar[0] ) 
    {
        dfs3( dfsAns.second.second, dfsAns.second.first, 0 ); 

        cnt = 0; 
        dfs3( dfsAns.second.first, dfsAns.second.second, 1 );

        for( auto &i : ans )
            if( i == 0 )
                i = map[2]; 
    }
    
    return ans ; 

}

vector<int> is_a_graph ( int a, int b, int c, int n, vector<vector<int>> &G)
{
    for( int i = 0 ; i < n ; i++ ) 
    {
        vector<vector<int>> g(n + 1);

        function<void(int)> dfs1 = [&]( int nod )
        {
            for( auto target : G[nod] ) 
            {
                if( !g[target].empty() )
                    continue ; 

                g[nod].push_back(target);
                g[target].push_back(nod); 
                dfs1(target); 
            }
        } ;

        dfs1( i ); 

        vector<int> ans = is_a_tree(a, b, c, n, g); 

        if( ans != vector<int>(n, 0) )
            return ans ; 
    }

    return vector<int> (n, 0);
}

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 if( degree == 2 )
        return is_a_line(a, b, c, n, G);

    else if( m == n - 1 ) 
        return is_a_tree(a, b, c, n, G);

    else //if( n <= 2500 and m <= 5000 ) 
        return is_a_graph(a, b, c, n, G);

}

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