Submission #1001420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001420		irmuun	Split the Attractions (IOI19_split)	C++17	22 / 100	567 ms	1048576 KiB

split

#include<bits/stdc++.h>
#include "split.h"

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=1e5+5;

int cur=0;
vector<int>adj[N],ord,sub(N,0),v[2],par(N,0);
vector<bool>used(N,0);
void dfs(int x){
    used[x]=true;
    sub[x]=1;
    ord.pb(x);
    for(int y:adj[x]){
        if(!used[y]){
            par[y]=x;
            dfs(y);
            sub[x]+=sub[y];
        }
    }
}
void dfs2(int x,int p){
    v[cur].pb(x);
    for(int y:adj[x]){
        if(y!=p){
            dfs2(y,x);
        }
    }
}

vector<int>find_split(int n, int a, int b, int c, vector<int>p, vector<int>q){
    int m=p.size();
    for(int i=0;i<m;i++){
        adj[p[i]].pb(q[i]);
        adj[q[i]].pb(p[i]);
    }
    vector<pair<int,int>>s(3);
    s[0]={a,1};
    s[1]={b,2};
    s[2]={c,3};
    sort(all(s));
    dfs(0);
    bool ok=false;
    vector<int>ans(n,0);
    for(int i=1;i<n;i++){
        if(sub[i]>=s[0].ff&&n-sub[i]>=s[1].ff){
            cur=0;
            dfs2(i,par[i]);
            cur=1;
            dfs2(par[i],i);
            break;
        }
        if(sub[i]>=s[1].ff&&n-sub[i]>=s[0].ff){
            cur=1;
            dfs2(i,par[i]);
            cur=0;
            dfs2(par[i],i);
            break;
        }
    }
    if(v[0].empty()){
        return ans;
    }
    for(int i=0;i<s[0].ff;i++){
        ans[v[0][i]]=s[0].ss;
    }
    for(int i=0;i<s[1].ff;i++){
        ans[v[1][i]]=s[1].ss;
    }
    for(int i=0;i<n;i++){
        if(ans[i]==0){
            ans[i]=3;
        }
    }
    return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:51:10: warning: unused variable 'ok' [-Wunused-variable]
   51 |     bool ok=false;
      |          ^~

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