oj.uz

Submission #293125

# Submission time Handle Problem Language Result Execution time Memory
293125 2020-09-07T16:37:49 Z Leonardo16 Split the Attractions (IOI19_split) C++14
18 / 100
 154 ms 23736 KB 
///   Code by Leonardo16
/// “Your focus determines your reality.” – Qui-Gon Jinn
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
//#pragma GCC option("arch=native","tune=native","no-zero-upper")
//#pragma GCC target("avx2")
//#define int  long long
#define ll long long
#define sz size
#define ull unsigned long long
#define ld long double
#define ii pair<int,int>
#define fst first
#define scd second
#define vi vector<int>
#define vii vector<ii>
#define pb push_back
#define pf push_front
#define fl '\n'
#define el endl
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
/// Functions
#define db(x) cerr << #x << ": " << (x) << '\n';
#define random() __builtin_ia32_rdtsc()
#define lg2(x) 31-__builtin_clz(x)
#define lg2ll(x) 63-__builtin_clzll(x)
#define pi acos(-1)
#define YN(x) cout<<((x)?("YES"):("NO"))<<fl;
#define yn(x) cout<<((x)?("Yes"):("No"))<<fl;
#define des(x,s1,s2,end1,end2) cout<<((x)?(s1):(s2))<<fl;if(x){end1;}else{end2;}
#define precision(x) cout.setf(ios::fixed);cout.precision(x);
/// Red-Black Tree Template
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
//#define less_than(n) order_of_key(n)
//#define en_pos(n) find_by_order(n)
/// Prime numbers  173,179,311,331,737,1009,2011,2027,3079,4001,100003
///=====================================================================
vi g[200005];
bool mk[200005];
int n,a,b,c;

int dp[200005];

bool found=false;
bool mk2[200005];

vi vb,va,vc;

void dfb(int u){
    if(vb.sz()<b)vb.pb(u);
    else return;
    mk2[u]=true;
    for(auto v:g[u]){
        if(mk2[v])continue;
        dfb(v);
    }
}


void dfa(int u){
    if(va.sz()<a)va.pb(u);
    else return;
    mk2[u]=true;
    for(auto v:g[u]){
        if(mk2[v])continue;
        dfa(v);
    }
}


void dfc(int u){
    if(vc.sz()<c)vc.pb(u);
    else return;
    mk2[u]=true;
    for(auto v:g[u]){
        if(mk2[v])continue;
        dfc(v);
    }
}



void dfsab(int u){
    mk[u]=true;

    dp[u]=1;
    int p=-1;
    for(auto v:g[u]){
        if(mk[v]){p=v;continue;}
        dfsab(v);
        dp[u]+=dp[v];
    }



    if(!found && dp[u]>=a && n-dp[u]>=b){
        found=true;
        mk2[u]=1;
        dfb(p);
        va.pb(u);
        for(auto v:g[u]){
            if(v!=p){
                dfa(v);
            }
        }
    }
}


void dfsac(int u){
    mk[u]=true;

    dp[u]=1;
    int p=-1;
    for(auto v:g[u]){
        if(mk[v]){p=v;continue;}
        dfsac(v);
        dp[u]+=dp[v];
    }



    if(!found && dp[u]>=a && n-dp[u]>=c){
        found=true;
        mk2[u]=1;
        dfc(p);
        va.pb(u);
        for(auto v:g[u]){
            if(v!=p){
                dfa(v);
            }
        }
    }
}


void dfsbc(int u){
    mk[u]=true;

    dp[u]=1;
    int p=-1;
    for(auto v:g[u]){
        if(mk[v]){p=v;continue;}
        dfsbc(v);
        dp[u]+=dp[v];
    }



    if(!found && dp[u]>=b && n-dp[u]>=c){
        found=true;
        mk2[u]=1;
        dfc(p);
        vb.pb(u);
        for(auto v:g[u]){
            if(v!=p){
                dfb(v);
            }
        }
    }
}


vi find_split(int nn,int aa,int bb,int cc,vi p,vi q){
    n=nn;a=aa;b=bb;c=cc;

    vi sol;

    for(int i=0;i<n;i++){
        sol.pb(0);
    }
    for(int i=0;i<p.sz();i++){
        g[p[i]].pb(q[i]);
        g[q[i]].pb(p[i]);
    }



    dfsab(0);


    if(va.sz()>0){
        for(auto it:va){
            sol[it]=1;
        }

        for(auto it:vb){
            sol[it]=2;
        }


        for(int i=0;i<n;i++){
            if(sol[i]==0){
                sol[i]=3;
            }
        }
        if(va.sz()==0){
            for(int i=0;i<n;i++){
                sol[i]=0;
            }
        }

        return sol;
    }


    va.clear();
    vb.clear();
    vc.clear();
    for(int i=0;i<=n;i++){
        mk[i]=0;
        dp[i]=0;
        mk2[i]=0;
        sol[i]=0;
    }


    dfsac(0);


    if(va.sz()>0){
        for(auto it:va){
            sol[it]=1;
        }

        for(auto it:vc){
            sol[it]=3;
        }


        for(int i=0;i<n;i++){
            if(sol[i]==0){
                sol[i]=2;
            }
        }
        if(va.sz()==0){
            for(int i=0;i<n;i++){
                sol[i]=0;
            }
        }

        return sol;
    }


    va.clear();
    vb.clear();
    vc.clear();
    for(int i=0;i<=n;i++){
        mk[i]=0;
        dp[i]=0;
        mk2[i]=0;
        sol[i]=0;
    }


    dfsbc(0);


    if(vb.sz()>0){
        for(auto it:vb){
            sol[it]=2;
        }

        for(auto it:vc){
            sol[it]=3;
        }


        for(int i=0;i<n;i++){
            if(sol[i]==0){
                sol[i]=1;
            }
        }
        if(va.sz()==0){
            for(int i=0;i<n;i++){
                sol[i]=0;
            }
        }

        return sol;
    }

    return sol;
}

//main(){
//    find_split(6, 2, 2, 2, {0, 0, 0, 0, 0}, {1, 2, 3, 4, 5});
//
//}

Compilation message

split.cpp: In function 'void dfb(int)':
split.cpp:55:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     if(vb.sz()<b)vb.pb(u);
      |        ~~~~~~~^~
split.cpp: In function 'void dfa(int)':
split.cpp:66:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |     if(va.sz()<a)va.pb(u);
      |        ~~~~~~~^~
split.cpp: In function 'void dfc(int)':
split.cpp:77:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |     if(vc.sz()<c)vc.pb(u);
      |        ~~~~~~~^~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:177:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for(int i=0;i<p.sz();i++){
      |                 ~^~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB ok, correct split
2 Correct 4 ms 4992 KB ok, correct split
3 Correct 4 ms 4992 KB ok, correct split
4 Correct 4 ms 4992 KB ok, correct split
5 Correct 4 ms 4992 KB ok, correct split
6 Correct 4 ms 4992 KB ok, correct split
7 Correct 129 ms 23072 KB ok, correct split
8 Correct 154 ms 20152 KB ok, correct split
9 Correct 120 ms 18544 KB ok, correct split
10 Correct 115 ms 23088 KB ok, correct split
11 Correct 139 ms 23736 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB ok, correct split
2 Correct 4 ms 4992 KB ok, correct split
3 Correct 4 ms 4992 KB ok, correct split
4 Correct 141 ms 17648 KB ok, correct split
5 Correct 116 ms 11332 KB ok, correct split
6 Correct 114 ms 23152 KB ok, correct split
7 Correct 121 ms 21488 KB ok, correct split
8 Correct 141 ms 13472 KB ok, correct split
9 Correct 94 ms 11248 KB ok, correct split
10 Correct 78 ms 11504 KB ok, correct split
11 Correct 60 ms 11504 KB ok, correct split
12 Correct 61 ms 11608 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB ok, correct split
2 Incorrect 111 ms 10864 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4992 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB ok, correct split
2 Correct 4 ms 4992 KB ok, correct split
3 Correct 4 ms 4992 KB ok, correct split
4 Correct 4 ms 4992 KB ok, correct split
5 Correct 4 ms 4992 KB ok, correct split
6 Correct 4 ms 4992 KB ok, correct split
7 Correct 129 ms 23072 KB ok, correct split
8 Correct 154 ms 20152 KB ok, correct split
9 Correct 120 ms 18544 KB ok, correct split
10 Correct 115 ms 23088 KB ok, correct split
11 Correct 139 ms 23736 KB ok, correct split
12 Correct 5 ms 4992 KB ok, correct split
13 Correct 4 ms 4992 KB ok, correct split
14 Correct 4 ms 4992 KB ok, correct split
15 Correct 141 ms 17648 KB ok, correct split
16 Correct 116 ms 11332 KB ok, correct split
17 Correct 114 ms 23152 KB ok, correct split
18 Correct 121 ms 21488 KB ok, correct split
19 Correct 141 ms 13472 KB ok, correct split
20 Correct 94 ms 11248 KB ok, correct split
21 Correct 78 ms 11504 KB ok, correct split
22 Correct 60 ms 11504 KB ok, correct split
23 Correct 61 ms 11608 KB ok, correct split
24 Correct 4 ms 4992 KB ok, correct split
25 Incorrect 111 ms 10864 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -