Submission #1035498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035498		Abito	Split the Attractions (IOI19_split)	C++17	0 / 100	578 ms	1048576 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
using namespace std;
const int N=2e5+5;
int n,a,b,c,sz[N],tin[N],t,mn,tree[N],h[3]={1,2,3},bh;
vector<int> adj[N],v,ans,A,B,C;
pair<int,int> bs[N];
bool vis[N];
bool cmp(int x,int y){
    int hx,hy;
    if (x==1) hx=a;
    if (x==2) hx=b;
    if (x==3) hx=c;
    if (y==1) hy=a;
    if (y==2) hy=b;
    if (y==3) hy=c;
    return hx<hy;
}
int getsz(int x,int p){
    sz[x]=1;
    for (auto u:adj[x]) if (u!=p) sz[x]+=getsz(u,x);
    return sz[x];
}
void dfs(int x,int p){
    tin[x]=++t;
    sz[x]=1;
    tree[t]=x;
    for (auto u:adj[x]){
        if (u==p) continue;
        dfs(u,x);
        sz[u]+=sz[x];
    }
    return;
}
void getb(int x,int p){
    bh--;
    ans[x-1]=h[1];
    if (!bh) return;
    for (auto u:adj[x]){
        if (u==p || ans[u-1]) continue;
        getb(u,x);
    }return;
}
vector<int> find_split(int NN,int aa,int bb,int cc,vector<int> Q,vector<int> P){
    n=NN,a=aa,b=bb,c=cc;
    mn=min(min(a,b),c);
    for (int i=0;i<Q.size();i++){
        int x=Q[i]+1,y=P[i]+1;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for (int i=0;i<n;i++) ans.pb(0);
    getsz(1,0);
    vector<int> best={n,1,1};
    for (int i=1;i<=n;i++){
        bs[i]={n,1};
        if (sz[i]>=mn) bs[i]={sz[i],1};
        for (auto u:adj[i]){
            if (sz[u]>sz[i]) continue;
            if (n-sz[u]>=mn) bs[i]=min(bs[i],{n-sz[u],u});
        }
        best=min(best,{bs[i].F,bs[i].S,i});
    }
    if (best[0]==n) return ans;
    sort(h,h+3,cmp);
    dfs(best[1],0);
    for (int i=tin[best[2]];i<=tin[best[2]]+mn-1;i++) ans[tree[i]-1]=h[0];
    if (h[1]==1) bh=a;
    if (h[1]==2) bh=b;
    if (h[1]==3) bh=c;
    if (!ans[0]) getb(best[1],0);
    for (int i=0;i<n;i++) if (!ans[i]) ans[i]=h[2];
    for (int i=0;i<n;i++){
        if (ans[i]==1) a--;
        if (ans[i]==2) b--;
        if (ans[i]==3) c--;
    }
    if (a || b || c){
        for (int i=0;i<n;i++) ans[i]=0;
    }
    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:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int i=0;i<Q.size();i++){
      |                  ~^~~~~~~~~
split.cpp: In function 'bool cmp(int, int)':
split.cpp:20:15: warning: 'hy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |     return hx<hy;
      |               ^~
split.cpp:20:15: warning: 'hx' may be used uninitialized in this function [-Wmaybe-uninitialized]

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