Submission #859988

#	Time	Username	Problem	Language	Result	Execution time	Memory
859988		abcvuitunggio	Split the Attractions (IOI19_split)	C++17	100 / 100	105 ms	32872 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int n,a,b,c,label[3]={1,2,3},d[100001],up[100001],sz[100001],vis[100001],node,t,f[100001],ch[100001],tin[100001],tout[100001];
vector <int> ke[100001],child[100001],del2[100001],res,ve;
vector <pair <int, int>> add[100001],del[100001];
void dfs(int u){
    tin[u]=++t;
    vis[u]=sz[u]=1;
    for (int v:ke[u])
        if (!vis[v]){
            child[u].push_back(v);
            d[v]=d[u]+1;
            up[v]=u;
            dfs(v);
            sz[u]+=sz[v];
        }
    tout[u]=t;
}
void dfs2(int u, int cur, int i){
    if (d[up[u]]<d[cur]){
        add[cur].push_back({u,i});
        del[up[u]].push_back({u,i});
        cur=up[u];
    }
    for (int v:child[u])
        dfs2(v,cur,i);
}
void dfs3(int u){
    if (ch[u])
        return;
    ve.push_back(u);
    for (int v:child[u])
        dfs3(v);
}
void update(int i, int val){
    i++;
    for (;i<=n;i+=i&(-i))
        f[i]+=val;
}
int get(int i){
    i++;
    int res=0;
    for (;i;i-=i&(-i))
        res+=f[i];
    return res;
}
bool check(int l, int r){
    vector <int> ve;
    set <pair <int, int>> s;
    set <int> s2;
    for (int i=0;i<n;i++){
        if (sz[i]>=l&&sz[i]<=r){
            node=i;
            return true;
        }
        add[i].clear();
        del[i].clear();
        del2[i].clear();
        if (sz[i]>r)
            ve.push_back(i);
    }
    memset(f,0,sizeof(f));
    memset(ch,0,sizeof(ch));
    sort(ve.begin(),ve.end(),[](int i, int j){return d[i]<d[j];});
    for (int i=0;i<ve.size();i++){
        for (int j:child[ve[i]])
            if (sz[j]<l)
                dfs2(j,ve[i],i);
        del2[up[ve[i]]].push_back(i);
    }
    s.insert({0,ve.size()});
    for (int i=ve.size()-1;i>=0;i--){
        for (auto [j,k]:del[ve[i]]){
            update(k,-sz[j]);
            s2.erase(j);
        }
        for (auto [j,k]:add[ve[i]]){
            update(k,sz[j]);
            s2.insert(j);
        }
        for (int j:del2[ve[i]])
            s.erase({-sz[ve[j]],j});
        auto it=s.lower_bound({a-sz[ve[i]],-1});
        auto [val,pos]=*it;
        if (sz[ve[i]]+val<=b){
            node=ve[i];
            if (pos<ve.size())
                ch[ve[pos]]=1;
            return true;
        }
        if (sz[ve[i]]+val-get(pos-1)<=r){
            node=ve[i];
            if (pos<ve.size())
                ch[ve[pos]]=1;
            int cnt=sz[ve[i]]+val;
            for (int j:s2){
                if (pos<ve.size()&&tin[ve[pos]]<=tin[j]&&tout[ve[pos]]>=tout[j])
                    continue;
                cnt-=sz[j];
                ch[j]=1;
                if (cnt<=r)
                    break;
            }
            return true;
        }
        s.insert({-sz[ve[i]],i});
    }
    return false;
}
vector <int> find_split(int N, int A, int B, int C, vector <int> p, vector <int> q){
	n=N,a=A,b=B,c=C;
	if (a>b){
        swap(a,b);
        swap(label[0],label[1]);
	}
	if (b>c){
        swap(b,c);
        swap(label[1],label[2]);
	}
	if (a>b){
        swap(a,b);
        swap(label[0],label[1]);
	}
	for (int i=0;i<p.size();i++){
        ke[p[i]].push_back(q[i]);
        ke[q[i]].push_back(p[i]);
	}
	dfs(0);
    for (int i=0;i<n;i++)
        for (int j:ke[i])
            if (d[j]<d[up[i]])
                up[i]=j;
    res.assign(n,0);
    if (check(b,n-a)){
        swap(a,b);
        swap(label[0],label[1]);
    }
    else if (!check(a,n-b))
        return res;
    dfs3(node);
    sort(ve.begin(),ve.end(),[](int i, int j){return d[i]<d[j];});
    for (int i=0;i<ve.size();i++)
        res[ve[i]]=label[(i>=a)*2];
    ve.clear();
    for (int i=0;i<n;i++)
        if (!res[i])
            ve.push_back(i);
    queue <int> Q;
    memset(d,0,sizeof(d));
    d[ve[0]]=1;
    Q.push(ve[0]);
    while (!Q.empty()){
        int u=Q.front();
        Q.pop();
        for (int v:ke[u])
            if (!res[v]&&!d[v]){
                d[v]=d[u]+1;
                Q.push(v);
            }
    }
    sort(ve.begin(),ve.end(),[](int i, int j){return d[i]<d[j];});
    for (int i=0;i<ve.size();i++)
        res[ve[i]]=label[(i>=b)+1];
    return res;
}

Compilation message (stderr)

split.cpp: In function 'bool check(int, int)':
split.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i=0;i<ve.size();i++){
      |                  ~^~~~~~~~~~
split.cpp:88:20: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             if (pos<ve.size())
      |                 ~~~^~~~~~~~~~
split.cpp:94:20: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |             if (pos<ve.size())
      |                 ~~~^~~~~~~~~~
split.cpp:98:24: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |                 if (pos<ve.size()&&tin[ve[pos]]<=tin[j]&&tout[ve[pos]]>=tout[j])
      |                     ~~~^~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:125:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |  for (int i=0;i<p.size();i++){
      |               ~^~~~~~~~~
split.cpp:143:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for (int i=0;i<ve.size();i++)
      |                  ~^~~~~~~~~~
split.cpp:163:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for (int i=0;i<ve.size();i++)
      |                  ~^~~~~~~~~~

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