Submission #1088742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088742		urd05	Split the Attractions (IOI19_split)	C++17	64 / 100	165 ms	182756 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> P;
vector<P> edge;
vector<int> tree[1000005];
int ind[3];
int p[1000005];
int sz[1000005];
vector<int> ret;

int find(int a) {
    return p[a]<0?a:p[a]=find(p[a]);
}

void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a!=b) {
        p[a]+=p[b];
        p[b]=a;
    }
}

void get_sz(int v,int pr) {
    sz[v]=1;
    for(int nt:tree[v]) {
        if (nt!=pr) {
            get_sz(nt,v);
            sz[v]+=sz[nt];
        }
    }
}

int get_cent(int v,int pr,int half) {
    for(int nt:tree[v]) {
        if (nt==pr) {
            continue;
        }
        if (sz[nt]>half) {
            return get_cent(nt,v,half);
        }
    }
    return v;
}

bool vis[1000005];
bool vis1[1000005];

void bfs0(int v,int pr,int k,int x) {
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(v);
    vis[v]=true;
    for(int i=0;i<k;i++) {
        int now=q.front();
        q.pop();
        ret[now]=x;
        for(int nt:tree[now]) {
            if (nt!=pr&&!vis[nt]) {
                q.push(nt);
                vis[nt]=true;
            }
        }
    }
}

int type[1000005];

void dfs_type(int v,int pr,int x) {
    type[v]=x;
    for(int nt:tree[v]) {
        if (nt!=pr) {
            dfs_type(nt,v,x);
        }
    }
}

vector<int> adj[1000005];
vector<int> adj1[1000005];

void bfs1(int v,int k,int x) {
    queue<int> q;
    q.push(v);
    memset(vis1,0,sizeof(vis1));
    vis1[v]=true;
    for(int i=0;i<k;i++) {
        int now=q.front();
        q.pop();
        ret[now]=x;
        for(int nt:adj[now]) {
            if (vis[type[nt]]&&!vis1[nt]) {
                q.push(nt);
                vis1[nt]=true;
            }
        }
    }
}

void bfs2(int v,int k,int x) {
    queue<int> q;
    q.push(v);
    memset(vis1,0,sizeof(vis1));
    vis1[v]=true;
    for(int i=0;i<k;i++) {
        int now=q.front();
        q.pop();
        ret[now]=x;
        for(int nt:adj[now]) {
            if (!vis[type[nt]]&&!vis1[nt]) {
                q.push(nt);
                vis1[nt]=true;
            }
        }
    }
}

vector<int> vec;
queue<int> q;

vector<int> find_split(int n, int a, int b, int c, vector<int> pp, vector<int> qq) {
    for(int i=0;i<3;i++) {
        ind[i]=i+1;
    }
    if (b>c) {
        swap(b,c);
        swap(ind[1],ind[2]);
    }
    if (a>b) {
        swap(a,b);
        swap(ind[0],ind[1]);
    }
    if (b>c) {
        swap(b,c);
        swap(ind[1],ind[2]);
    }
    ret.resize(n);
    for(int i=0;i<n;i++) {
        ret[i]=ind[2];
    }
    for(int i=0;i<pp.size();i++) {
        adj[pp[i]].push_back(qq[i]);
        adj[qq[i]].push_back(pp[i]);
        edge.push_back(P(pp[i],qq[i]));
    }
    memset(p,-1,sizeof(p));
    for(P x:edge) {
        if (find(x.first)!=find(x.second)) {
            merge(x.first,x.second);
            tree[x.first].push_back(x.second);
            tree[x.second].push_back(x.first);
        }
    }
    get_sz(0,-1);
    int ct=get_cent(0,-1,n/2);
    get_sz(ct,-1);
    type[ct]=ct;
    for(int nt:tree[ct]) {
        if (sz[nt]>=a) {
            bfs0(nt,ct,a,ind[0]);
            bfs0(ct,nt,b,ind[1]);
            return ret;
        }
        dfs_type(nt,ct,nt);
    }
    memset(vis,0,sizeof(vis));
    for(P x:edge) {
        if (x.first==ct||x.second==ct) {
            continue;
        }
        if (type[x.first]!=type[x.second]) {
            adj1[type[x.first]].push_back(type[x.second]);
            adj1[type[x.second]].push_back(type[x.first]);
        }
    }
    memset(vis,0,sizeof(vis));
    for(int nxt:tree[ct]) {
        if (vis1[nxt]) {
            continue;
        }
        q.push(nxt);
        vis[nxt]=true;
        int x=0;
        while (!q.empty()) {
            int now=q.front();
            vec.push_back(now);
            q.pop();
            x+=sz[now];
            if (x>=a) {
                if (x<=n/2) {
                    bfs1(now,a,ind[0]);
                    bfs2(ct,b,ind[1]);
                }
                else {
                    bfs1(now,b,ind[1]);
                    bfs2(ct,a,ind[0]);
                }
                return ret;
            }
            for(int nt:adj1[now]) {
                if (!vis[nt]) {
                    vis[nt]=true;
                    q.push(nt);
                }
            }
        }
        for(int x:vec) {
            vis[x]=false;
            vis1[x]=true;
        }
        vec.clear();
    }
    for(int i=0;i<n;i++) {
        ret[i]=0;
    }
    return ret;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:142:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int i=0;i<pp.size();i++) {
      |                 ~^~~~~~~~~~

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