Submission #275396

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

split

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef double db;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define po pop_back
#define pb push_back
#define mk make_pair
#define mt make_tuple
#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
#define read(x) scanf("%lld",&x);
#define print(x) printf("%lld ",x);
#define endl '\n';
// 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;
            }
    }
    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:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for(int j=0; j<vv1.size(); j++){
      |                          ~^~~~~~~~~~~
split.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for(int j=0; j<vv2.size(); j++){
      |                          ~^~~~~~~~~~~
split.cpp:85:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                 for(int j=0; j<vv1.size(); j++){
      |                              ~^~~~~~~~~~~
split.cpp:89:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                 for(int j=0; j<vv2.size(); j++){
      |                              ~^~~~~~~~~~~

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