Submission #296655

#	Time	Username	Problem	Language	Result	Execution time	Memory
296655		mat_v	Split the Attractions (IOI19_split)	C++14	22 / 100	622 ms	1048580 KiB

split

//#include "split.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define maxn 200005

using namespace std;
using namespace __gnu_pbds;
typedef tree<pii, null_type, less<pii>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


vector<int> graf[maxn];

int N, M;
int subtr[maxn];
int cale[maxn];

void dfs(int x, int last){
    subtr[x] = 1;
    cale[x] = last;
    for(auto c:graf[x]){
        if(c == last)continue;
        dfs(c, x);
        subtr[x] += subtr[c];
    }
}


int ost[5];
int sol[maxn];
int fr, se, tr;
void oboji(int x, int last){
    if(ost[fr]){
        ost[fr]--;
        sol[x] = fr;
    }
    else{
        sol[x] = tr;
    }
    for(auto c:graf[x]){
        if(c == last)continue;
        oboji(c, x);
    }
}

void dfs2(int x){
    if(x < 1)return;
    if(ost[se]){
        ost[se]--;
        sol[x] = se;
    }
    else sol[x] = tr;
    for(auto c:graf[x]){
        if(sol[c] != 0)continue;
        dfs2(c);
    }
}


bool mark[maxn];

int brat;

void dfs3(int x, int last){
    mark[x] = 1;
    for(auto c:graf[x]){
        if(c == last)continue;
        if(mark[c])brat = c;
        else dfs3(c, x);
    }
}

void dfs4(int x){
    mark[x] = 1;
    if(ost[2]){
        ost[2]--;
        sol[x] = 2;
    }
    else sol[x] = 3;
    for(auto c:graf[x]){
        if(mark[c])continue;
        dfs4(c);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    N = n;
    M = p.size();
    for(int i=0; i<M; i++){
        int p1 = p[i] + 1;
        int q1 = q[i] + 1;
        graf[p1].pb(q1);
        graf[q1].pb(p1);
    }

    if(1 == 1){
        dfs(1,-1);
        int sef = -1;
        int mini1 = min(a, min(b,c));
        int mini2;
        if(a == mini1)mini2 = min(b,c);
        if(b == mini1)mini2 = min(a,c);
        if(c == mini1)mini2 = min(a,b);

        //cout << mini1 << " " << mini2 << "\n";

        ff(i,1,n){
            int p1 = subtr[i];
            int p2 = n - subtr[i];
            if(p1 >= mini1 && p2 >= mini2){
                sef = i;
                break;
            }
            if(p1 >= mini2 && p2 >= mini1){
                sef = i;
                break;
            }
        }


        if(sef == -1){
            vector<int> kurac;
            ff(i,0,n - 1)kurac.pb(0);
            return kurac;
        }
        ost[1] = a;
        ost[2] = b;
        ost[3] = c;
        int p1 = subtr[sef];
        int p2 = n - p1;
        fr = 0, se = 0;
        if(p1 >= mini1 && p2 >= mini2){
            if(mini1 == a)fr = 1;
            if(mini1 == b)fr = 2;
            if(mini1 == c)fr = 3;
            if(mini2 == a && fr != 1)se = 1;
            if(mini2 == b && fr != 2)se = 2;
            if(mini2 == c && fr != 3)se = 3;

        }
        else if(p2 >= mini1 && p1 >= mini1){
            if(mini2 == a)fr = 1;
            if(mini2 == b)fr = 2;
            if(mini2 == c)fr = 3;
            if(mini1 == a && fr != 1)se = 1;
            if(mini1 == b && fr != 2)se = 2;
            if(mini1 == c && fr != 3)se = 3;
        }
        tr = 6 - fr - se;
        oboji(sef, cale[sef]);
       // cout << sef << " " << fr << " " << se << " " << tr << "\n";
        dfs2(cale[sef]);
        vector<int> res;
        ff(i,1,n)res.pb(sol[i]);
        return res;
    }
    else if(a == 1){
        dfs3(1, -1);
        assert(brat >= 1 && brat <= n);
        sol[brat] = 1;
        ff(i,1,n)mark[i] = 0;
        mark[brat] = 1;
        ost[2] = b;
        ost[3] = c;
        if(brat == 1)dfs4(2);
        else dfs4(1);

        vector<int> ans;
        ff(i,1,n)ans.pb(sol[i]);
        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:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
split.cpp:119:9: note: in expansion of macro 'ff'
  119 |         ff(i,1,n){
      |         ^~
split.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
split.cpp:135:13: note: in expansion of macro 'ff'
  135 |             ff(i,0,n - 1)kurac.pb(0);
      |             ^~
split.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
split.cpp:166:9: note: in expansion of macro 'ff'
  166 |         ff(i,1,n)res.pb(sol[i]);
      |         ^~
split.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
split.cpp:173:9: note: in expansion of macro 'ff'
  173 |         ff(i,1,n)mark[i] = 0;
      |         ^~
split.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
split.cpp:181:9: note: in expansion of macro 'ff'
  181 |         ff(i,1,n)ans.pb(sol[i]);
      |         ^~
split.cpp:150:13: warning: 'mini2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  150 |             if(mini2 == c && fr != 3)se = 3;
      |             ^~

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