Submission #822977

#	Time	Username	Problem	Language	Result	Execution time	Memory
822977		vjudge1	Split the Attractions (IOI19_split)	C++14	11 / 100	63 ms	12740 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 ;
bool us[N + 1] ;
vector<int> res, 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_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) ;
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> fr, vector<int> to)
{
    bool flag1 = 0, flag2 = 0 ;
    for(int i = 0 ; i < n ; i++)
        res.push_back(0) ;
    int m = fr.size() ;
    for(int i = 0 ; i < m ; 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)
    {
    }
    if(a == 1)
    {
        int ind ;
        for(int i = 0 ; i < n ; i++)
        {
            if(us[i])
                continue ;
            cnt = 0 ;
            dfs(i) ;
            if(cnt >= min(b, c))
            {
                ind = i ;
                flag2 = 1 ;
            }
        }
        if(!flag2)
            return res ;
        else
        {
            ultra_clear() ;
            if(b <= c)
                dfs_color(ind, 2, b) ;
            else
                dfs_color(ind, 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 ;
}
//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 ;
//}

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