Submission #615063

#	Time	Username	Problem	Language	Result	Execution time	Memory
615063		rrrr10000	Split the Attractions (IOI19_split)	C++14	100 / 100	187 ms	27068 KiB

split

// #include "split.h"
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define fi first
#define se second
#define pb emplace_back
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001;

vector<int> find_split(int n, int A, int B, int C, vector<int> U, vector<int> V) {
    vector<int> impossible(n);
	ll k=min({A,B,C});
    vvi g(n);
    rep(i,U.size()){
        g[U[i]].pb(V[i]);
        g[V[i]].pb(U[i]);
    }
    vi lk(n,inf),dep(n,-1),par(n),sub(n,1),euler;
    function<ll(ll,ll,ll)> dfs=[&](ll i,ll p,ll d){
        euler.pb(i);
        par[i]=p;dep[i]=d;
        for(ll x:g[i])if(x!=p){
            if(dep[x]==-1){
                sub[i]+=dfs(x,i,d+1);
                chmin(lk[i],lk[x]);
            }
            else chmin(lk[i],dep[x]);
        }
        return sub[i];
    };dfs(0,-1,0);
    
	auto sol=[&](ll sz,vector<bool> flag){
		ll i=0;
		while(!flag[i])i++;
		flag[i]=false;
		vi res;
		function<void(ll)> dfs=[&](ll cur){
			if(res.size()==sz)return;
			res.pb(cur);
			for(auto x:g[cur])if(flag[x]){
				flag[x]=false;
				dfs(x);
				if(res.size()==sz)return;
			}
		};dfs(i);
		return res;
	};
    auto answer=[&](vi al){
        vb f1(n,false),f2(n,false),f3(n,true);
        for(ll i:al)f1[i]=true;
        rep(i,n)if(!f1[i])f2[i]=true;
        if(al.size()*2>n)swap(f1,f2);
        vi a=sol(k,f1),b=sol(n-min({A,B,C})-max({A,B,C}),f2);
        for(ll i:a)f3[i]=false;
        for(ll i:b)f3[i]=false;
        vi c;rep(i,n)if(f3[i])c.pb(i);
        if(A!=a.size())swap(a,b);
        if(A!=a.size())swap(a,c);
        if(B!=b.size())swap(b,c);
        vector<int> res(n);
        for(ll i:a)res[i]=1;
        for(ll i:b)res[i]=2;
        for(ll i:c)res[i]=3;
        return res;
    };
    auto get_sub=[&](ll t){
        vi res;
        function<void(ll)> dfs=[&](ll i){
            res.pb(i);
            for(ll x:g[i])if(par[x]==i)dfs(x);
        };dfs(t);
        return res;
    };
    ll rt;
    for(ll i:euler)if(sub[i]*2>=n)rt=i;
    for(ll x:g[rt])if(par[x]==rt&&sub[x]>=k)return answer(get_sub(x));
    vi al;al.pb(rt);
    for(ll x:g[rt])if(par[x]==rt&&lk[x]>=dep[rt]){
        vi tmp=get_sub(x);
        for(ll y:tmp)al.pb(y);
    }
    if(al.size()>n-k)return impossible;
    for(ll x:g[rt])if(par[x]==rt&&lk[x]<dep[rt]&&al.size()<k){
        vi tmp=get_sub(x);
        for(ll y:tmp)al.pb(y);
    }
    return answer(al);
}

Compilation message (stderr)

split.cpp: In lambda function:
split.cpp:57:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   57 |    if(res.size()==sz)return;
      |       ~~~~~~~~~~^~~~
split.cpp:62:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   62 |     if(res.size()==sz)return;
      |        ~~~~~~~~~~^~~~
split.cpp: In lambda function:
split.cpp:71:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |         if(al.size()*2>n)swap(f1,f2);
      |            ~~~~~~~~~~~^~
split.cpp:76:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         if(A!=a.size())swap(a,b);
      |            ~^~~~~~~~~~
split.cpp:77:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         if(A!=a.size())swap(a,c);
      |            ~^~~~~~~~~~
split.cpp:78:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         if(B!=b.size())swap(b,c);
      |            ~^~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:101:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  101 |     if(al.size()>n-k)return impossible;
      |        ~~~~~~~~~^~~~
split.cpp:102:59: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  102 |     for(ll x:g[rt])if(par[x]==rt&&lk[x]<dep[rt]&&al.size()<k){
      |                                                  ~~~~~~~~~^~

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