Submission #295707

#	Time	Username	Problem	Language	Result	Execution time	Memory
295707		mat_v	Split the Attractions (IOI19_split)	C++14	0 / 100	630 ms	1048576 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);
    }
}

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

        ff(i,1,n){
            int p1 = subtr[i];
            int p2 = n - subtr[i];
            if(p1 >= mini1 && p2 >= mini2){
                sef = i;
                break;
            }
            if(p1 >= mini2 && p1 >= 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]);
        dfs2(cale[sef]);
        vector<int> res;
        ff(i,1,n)res.pb(sol[i]);
        return res;
    }
}

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:89:9: note: in expansion of macro 'ff'
   89 |         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:104:13: note: in expansion of macro 'ff'
  104 |             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:134:9: note: in expansion of macro 'ff'
  134 |         ff(i,1,n)res.pb(sol[i]);
      |         ^~
split.cpp:137:1: warning: control reaches end of non-void function [-Wreturn-type]
  137 | }
      | ^
split.cpp:119:13: warning: 'mini2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             if(mini2 == c && fr != 3)se = 3;
      |             ^~

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