Submission #825219

#	Time	Username	Problem	Language	Result	Execution time	Memory
825219		ZHIRDILBILDIZ	Split the Attractions (IOI19_split)	C++14	18 / 100	77 ms	25128 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 ;
bool us[N + 1] ;
int vert, sz[N + 1], ind[N + 1] ;
vector<int> ts, res, v[N + 1], other[N + 1], tree[N + 1] ;
void ultra_clear()
{
    for(int i = 1 ; i <= N ; i++)
        us[i] = 0 ;
}
void build_tree(int city)
{
    us[city] = 1 ;
    for(int i : v[city])
    {
        if(us[i])
            continue ;
        tree[city].push_back(i) ;
        build_tree(i) ;
    }
}
void dfs_for_tree(int city, int a1)
{
    ind[city] = ts.size() ;
    ts.push_back(city) ;
    sz[city]++ ;
    int mx = 0 ;
    for(int i : tree[city])
    {
        dfs_for_tree(i, a1) ;
        mx = max(mx, sz[i]) ;
        sz[city] += sz[i] ;
    }
    if(mx < a1 && sz[city] >= a1)
        vert = city ;
}
void dfs_color(int city, int &cnt, int color)
{
    us[city] = 1 ;
    if(cnt)
    {
        cnt-- ;
        res[city] = color ;
    }
    for(int i : tree[city])
    {
        if(us[i])
            continue ;
        dfs_color(i, cnt, color) ;
    }
}
vector<int> find_split(int n, int a, int b, int c, vector<int> fr, vector<int> to)
{
    vector<pair<int, int>> all = {{a, 1}, {b, 2}, {c, 3}} ;
    sort(all.begin(), all.end()) ;
    int m = fr.size() ;
    for(int i = 0 ; i < n ; i++)
        res.push_back(0) ;
    for(int i = 0 ; i < m ; i++)
    {
        v[fr[i]].push_back(to[i]) ;
        v[to[i]].push_back(fr[i]) ;
    }
    build_tree(0) ;
    dfs_for_tree(0, all[0].fi) ;
    for(int i = 0 ; i < m ; i++)
    {
        int f = fr[i], t = to[i] ;
        if(ind[vert] <= ind[f] && ind[f] < ind[vert] + sz[vert] && ind[t] < ind[vert])
            other[f].push_back(t) ;
        if(ind[vert] <= ind[t] && ind[t] < ind[vert] + sz[vert] && ind[f] < ind[vert])
            other[t].push_back(f) ;
    }
    vector<int> del ;
    for(int i = ind[vert] + 1 ; i < ind[vert] + sz[vert] ; i++)
    {
        int now = ts[i] ;
        if(sz[vert] - sz[now] >= all[0].fi && other[now].size())
        {
            del.push_back(now) ;
            tree[other[now][0]].push_back(now) ;
            us[now] = 1 ;
            sz[vert] -= sz[now] ;
            i = ind[now] + sz[now] - 1 ;
        }
    }
    if(sz[vert] >= all[0].fi && n - sz[vert] >= all[1].fi)
    {
        ultra_clear() ;
        dfs_color(vert, all[0].fi, all[0].se) ;
        for(int i : del)
            us[i] = 0 ;
        dfs_color(0, all[1].fi, all[1].se) ;
        for(int i = 0 ; i < n ; i++)
            if(!res[i])
                res[i] = all[2].se ;
    }
    return res ;
}
//signed main()
//{
//    ios_base::sync_with_stdio( 0 ) ;
//    cin.tie( 0 ) ;
//    cout.tie( 0 ) ;
//    int n, m, a, b, c ;
//    cin >> n >> a >> b >> c >> m ;
//    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: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36