Submission #253745

#	Time	Username	Problem	Language	Result	Execution time	Memory
253745		khangal	Split the Attractions (IOI19_split)	C++14	40 / 100	255 ms	40880 KiB

split

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
#define po pop_back
#define pb push_back
#define mk make_pair
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18
#define MIN -1e18
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,m,ans,mid,mn,mx,cnt,T,sum,h1,h2,e[1234567],b[1234567],c[1234567],d[1<<20],k,i,j,l,r,h,a[1234567],w,x,y,z;
bool used[1234567];
vector<int> v[1234567],vec,vv1,vv2;
string s1,s;
int sz[1234567],par[1234567];
ll dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},c1[123][123];
int dfs(int node , int p){
    if(sz[node] > 0) return 0;
    par[node] = p;
    sz[node] = 1;
    for(auto x : v[node]) sz[node] += dfs(x , node);
    return sz[node];
}
void dfs1(int node){
    used[node] = 1;
    vv1.pb(node);
    for(auto x : v[node]) if(par[x] == node) dfs1(x);
    return;
}
void dfs2(int node){
    if(used[node]) return;
    vv2.pb(node);
    for(auto x : v[node]) if(par[x] == node) dfs2(x);
    return;
}
vector<int> find_split(int n ,  int  a , int b ,int c  ,vector<int>v1 , vector<int>v2){
    int m = v1.size();
    for(int i=0; i<m; i++){
        v[v2[i]].pb(v1[i]);
        v[v1[i]].pb(v2[i]);
    }
    dfs(0,-1);
    vector<pair<int , int>> vv = {{a, 1}, {b, 2}, {c, 3}};
    sort(vv.begin(), vv.end());
    vector<int> ans(n, 0);
    for(int i=0; i<n; i++){
        if(sz[i] >= vv[0].ff && n-sz[i] >= vv[1].ff){
            dfs1(i);
            dfs2(0);
            for(int j=0; j<vv1.size(); j++){
                if(j < vv[0].ff) ans[vv1[j]] = vv[0].ss;
                else ans[vv1[j]] = vv[2].ss;
            }
            for(int j=0; j<vv2.size(); j++){
                if(j < vv[1].ff) ans[vv2[j]] = vv[1].ss;
                else ans[vv2[j]] = vv[2].ss;
            }
            return ans;
        } 
        else 
            if(sz[i] >= vv[1].ff && n-sz[i] >= vv[0].ff){
                dfs1(i);
                dfs2(0);
                for(int j=0; j<vv1.size(); j++){
                    if(j < vv[1].ff) ans[vv1[j]] = vv[1].ss;
                    else ans[vv1[j]] = vv[2].ss;
                }
                for(int j=0; j<vv2.size(); j++){
                    if(j < vv[0].ff) ans[vv2[j]] = vv[0].ss;
                    else ans[vv2[j]] = vv[2].ss;
            }
            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:64:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0; j<vv1.size(); j++){
                          ~^~~~~~~~~~~
split.cpp:68:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0; j<vv2.size(); j++){
                          ~^~~~~~~~~~~
split.cpp:78:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j=0; j<vv1.size(); j++){
                              ~^~~~~~~~~~~
split.cpp:82:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j=0; j<vv2.size(); j++){
                              ~^~~~~~~~~~~
split.cpp:89:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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