Submission #823089

#	Time	Username	Problem	Language	Result	Execution time	Memory
823089		vjudge1	Split the Attractions (IOI19_split)	C++14	40 / 100	90 ms	14664 KiB

split

#include<bits/stdc++.h>
#include "split.h"
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 1e5 ;
int cnt, ch[N + 1] ;
bool us[N + 1] ;
vector<int> res, komp, v[N + 1] ;
void ultra_clear()
{
    for(int i = 0 ; i < N ; i++)
        us[i] = 0 ;
}
void dfs(int city)
{
    cnt++ ;
    us[city] = 1 ;
    for(int i : v[city])
    {
        if(us[i])
            continue ;
        dfs(i) ;
    }
}
void dfs_save(int city)
{
    us[city] = 1 ;
    komp.push_back(city) ;
    for(int i : v[city])
    {
        if(us[i])
            continue ;
        dfs_save(i) ;
    }
}
void dfs_color(int city, int color, int& cnt)
{
    if(cnt)
    {
        res[city] = color ;
        cnt-- ;
    }
    us[city] = 1 ;
    for(int i : v[city])
    {
        if(us[i] || !cnt)
            continue ;
        dfs_color(i, color, cnt) ;
    }
}
void dfs_for_tree(int city, int last)
{
    for(int i : v[city])
    {
        if(i == last || us[i])
            continue ;
        dfs_for_tree(i, city) ;
        ch[city] += ch[i] ;
    }
    ch[city]++ ;
}
pair<int, int> spl = {-1, -1} ;
void dfs_check(int city, int last, int mn1, int mn2)
{
    for(int i : v[city])
    {
        if(i == last || us[i])
            continue ;
        if(ch[i] >= mn1 && ch[0] - ch[i] >= mn2 || ch[i] >= mn2 && ch[0] - ch[i] >= mn1)
            spl = {city, i} ;
        dfs_check(i, city, mn1, mn2) ;
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> fr, vector<int> to)
{
    vector<pair<int, int>> abu = {{a, 1}, {b, 2}, {c, 3}} ;
    sort(abu.begin(), abu.end()) ;
    bool flag1 = 0 ;
    for(int i = 0 ; i < n ; i++)
        res.push_back(0) ;
    for(int i = 0 ; i < fr.size() ; i++)
    {
        v[fr[i]].push_back(to[i]) ;
        v[to[i]].push_back(fr[i]) ;
        if(v[to[i]].size() > 2 || v[fr[i]].size() > 2)
            flag1 = 1 ;
    }
    if(!flag1)
    {
        for(int i = 0 ; i < n ; i++)
        {
            if(us[i] || v[i].size() == 2)
                continue ;
            cnt &= 0 ;
            dfs(i) ;
            if(cnt >= abu[0].fi + abu[1].fi)
            {
                ultra_clear() ;
                dfs_save(i) ;
                for(int j : komp)
                {
                    if(abu[0].fi)
                    {
                        res[j] = abu[0].se ;
                        abu[0].fi-- ;
                        continue ;
                    }
                    if(abu[1].fi)
                    {
                        res[j] = abu[1].se ;
                        abu[1].fi-- ;
                    }
                }
                for(int i = 0 ; i < n ; i++)
                    if(!res[i])
                        res[i] = abu[2].se ;
                return res ;
            }
        }
        for(int i = 0 ; i < n ; i++)
        {
            if(us[i])
                continue ;
            cnt &= 0 ;
            dfs(i) ;
            if(cnt >= abu[0].fi + abu[1].fi)
            {
                ultra_clear() ;
                dfs_save(i) ;
                for(int j : komp)
                {
                    if(abu[0].fi)
                    {
                        abu[0].fi-- ;
                        res[j] = abu[0].se ;
                        continue ;
                    }
                    if(abu[1].fi)
                    {
                        abu[1].fi-- ;
                        res[j] = abu[1].se ;
                    }
                }
                for(int i = 0 ; i < n ; i++)
                    if(!res[i])
                        res[i] = abu[2].se ;
                return res ;
            }
        }
        return res ;
    }
    if(a == 1)
    {
        ultra_clear() ;
        if(b <= c)
            dfs_color(1, 2, b) ;
        else
            dfs_color(1, 3, c) ;
        for(int i = 0 ; i < n ; i++)
            if(!res[i])
            {
                if(a)
                {
                    res[i] = 1 ;
                    a &= 0 ;
                }
                else
                {
                    if(b)
                        res[i] = 2 ;
                    else
                        res[i] = 3 ;
                }
            }
        return res ;
    }
    if(fr.size() < n)
    {
        dfs_for_tree(0, -1) ;
        dfs_check(0, -1, abu[0].fi, abu[1].fi) ;
//        cout<<spl.fi<<' '<<spl.se << '\n';
        if(spl.fi != -1 && spl.se != -1)
        {
            if(ch[spl.se] <= ch[0] - ch[spl.se])
            {
                us[spl.fi] = 1 ;
                dfs_color(spl.se, abu[0].se, abu[0].fi) ;
                us[spl.fi] = 0 ;
                us[spl.se] = 1 ;
                dfs_color(spl.fi, abu[1].se, abu[1].fi) ;
            }
            else
            {
                us[spl.se] = 1 ;
                dfs_color(spl.fi, abu[0].se, abu[0].fi) ;
                us[spl.se] = 0 ;
                us[spl.fi] = 1 ;
                dfs_color(spl.se, abu[1].se, abu[1].fi) ;
            }
            for(int i = 0 ; i < n ; i++)
                if(!res[i])
                    res[i] = abu[2].se ;
        }
    }
    return res ;
}
//signed main()
//{
//    ios_base::sync_with_stdio( 0 ) ;
//    cin.tie( 0 ) ;
//    cout.tie( 0 ) ;
//    int n, a, b, c, m ;
//    cin >> n >> m >> a >> b >> c ;
//    vector<int> fr(m), to(m) ;
//    for(int i = 0 ; i < m ; i++)
//        cin >> fr[i] >> to[i] ;
//    vector<int> ans = find_split(n, a, b, c, fr, to) ;
//    for(int i : ans)
//        cout << i << ' ' ;
//    return 0 ;
//}
//19 18
//8 5 6
//0 1
//1 2
//1 5
//5 4
//5 3
//5 6
//6 7
//7 8
//7 9
//6 13
//6 10
//6 11
//6 12
//6 14
//14 16
//14 17
//14 18
//14 15

Compilation message (stderr)

split.cpp: In function 'void dfs_check(int, int, int, int)':
split.cpp:71:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   71 |         if(ch[i] >= mn1 && ch[0] - ch[i] >= mn2 || ch[i] >= mn2 && ch[0] - ch[i] >= mn1)
      |            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 0 ; i < fr.size() ; i++)
      |                     ~~^~~~~~~~~~~
split.cpp:179:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  179 |     if(fr.size() < n)
      |        ~~~~~~~~~~^~~

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