Submission #991488

#	Time	Username	Problem	Language	Result	Execution time	Memory
991488		amine_aroua	Split the Attractions (IOI19_split)	C++17	0 / 100	39 ms	10200 KiB

split

#include <cstdio>
#include <cassert>
#include <bits/stdc++.h>
#define Int long long
#define fore(i , n) for(int i = 0 ; i<n;i++)
#define pb push_back
#define forn(i , x , y) for(int i = x ; i >= y; i--)
using namespace std;
vector<int> ans;
vector<bool> vis;
vector<vector<int>>adj;
int a , b , c;
bool acc = 0;
int cnt = 1;
void dfs(int x)
{
    if(vis[x])
        return ;
    if(cnt == b)
    {
        acc = 1;
    }
    if(cnt <= b)
        ans[x] = 2;
    else
    {
        return;
    }
    vis[x] = 1;
    for(auto u : adj[x])
    {
        if(!vis[u])
        {
            cnt++;
            dfs(u);
        }
    }
}
vector<int> find_split(int n, int _a , int _b , int _c , vector<int> p , vector<int> q)
{
    a = _a , b=_b , c = _c;
    if(b > c)
        swap(b , c);
    ans.assign(n , 0);
    vis.assign(n , 0);
    adj.assign(n , {});
    int m = (int)p.size();
    fore(i , m)
    {
        adj[p[i]].pb(q[i]);
        adj[q[i]].pb(p[i]);
    }
    vector<int> perm;
    fore(i , n)
        perm.pb(i);
    random_shuffle(perm.begin() , perm.end());
    for(auto node : perm)
    {
        vis.assign(n , 0);
        ans.assign(n , 3);
        ans[node] = 1;
        vis[node] = 1;
        acc = 0;
        for(auto u : adj[node])
        {
            cnt = 1;
            dfs(u);
            if(acc)
                break;
        }
        if(acc == 1)
        {
            if(_b > _c)
            {
                for(auto &x: ans)
                {
                    if(x == 2)
                        x = 3;
                    else if(x == 3)
                        x = 2;
                }
            }
            return ans;
        }
    }
    return vector<int>(n , 0);
}
//int main() {
//    int n, m, A, B, C;
//    assert(5 == scanf("%d%d%d%d%d", &n, &m, &A, &B, &C));
//    vector<int> p(m), q(m);
//    for (int i=0; i<m; i++)
//        assert(2 == scanf("%d%d", &p[i], &q[i]));
//    fclose(stdin);
//
//    vector<int> result = find_split(n, A, B, C, p, q);
//
//    for (int i=0; i<(int)result.size(); i++)
//        printf("%s%d", ((i>0)?" ":""), result[i]);
//    printf("\n");
//    fclose(stdout);
//    return 0;
//}

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