Submission #755622

#	Time	Username	Problem	Language	Result	Execution time	Memory
755622		Rafi22	Split the Attractions (IOI19_split)	C++14	0 / 100	2084 ms	31396 KiB

split

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=200007;

bool odw[N];
int s[N];
vector<int>G[N];
set<int>G1[N];
vector<pair<int,int>>E;
vector<int>ans;

void dfs(int v)
{
    odw[v]=1;
    s[v]=1;
    for(auto u:G[v])
    {
        if(!odw[u])
        {
            G1[v].insert(u);
            G1[u].insert(v);
            dfs(u);
            s[v]+=s[u];
        }
        else E.pb({u,v});
    }
}

int C;

void get(int v,int o,int k)
{
    if(C==0) return;
    ans[v]=k;
    C--;
    for(auto u:G1[v])
    {
        if(u==o) continue;
        get(u,v,k);
    }
}

vector<int> find_split(int n,int a,int b,int c,vector<int>P,vector<int>Q)
{
    vector<pair<int,int>>V;
    V.pb({a,1});
    V.pb({b,2});
    V.pb({c,3});
    sort(all(V));
    int A=V[0].st,B=V[1].st;
    for(int i=0;i<sz(P);i++)
    {
        G[P[i]].pb(Q[i]);
        G[Q[i]].pb(P[i]);
    }
    dfs(0);
    ans.resize(n,0);
    int v=0;
    bool is=0;
    while(true)
    {
        int mx=0,p=-1;
        for(auto u:G1[v])
        {
            if(s[u]>mx)
            {
                mx=s[u];
                p=u;
            }
        }
        if(mx<A) break;
        if(mx>=A&&n-mx>=B)
        {
            for(int i=0;i<n;i++) ans[i]=V[2].nd;
            C=A;
            get(p,v,V[0].nd);
            C=B;
            get(v,p,V[1].nd);
            is=1;
            break;
        }
        if(mx>=B&&n-mx>=A)
        {
            for(int i=0;i<n;i++) ans[i]=V[2].nd;
            C=B;
            get(p,v,V[0].nd);
            C=A;
            get(v,p,V[1].nd);
            is=1;
            break;
        }
        v=p;
    }
    return ans;
}
/*
int main()
{
    vector<int>V=find_split(9, 4, 2, 3, {0, 0, 0, 0, 0, 0, 1, 3, 4, 5},{1, 2, 3, 4, 6, 8, 7, 7, 5, 6});
    for(auto x:V) cout<<x<<" ";
    cout<<endl;
    return 0;
}
*/

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:72:10: warning: variable 'is' set but not used [-Wunused-but-set-variable]
   72 |     bool is=0;
      |          ^~

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