Submission #413053

#	Time	Username	Problem	Language	Result	Execution time	Memory
413053		ismoilov	Split the Attractions (IOI19_split)	C++14	100 / 100	162 ms	24900 KiB

split

#include "split.h"

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//#define int ll
#define ve vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
#define fv(a, c) for(int (a) = (1); (a) <= (c); (a)++)
#define fz(a, c) for(int (a) = (0); (a) < (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) > (c); (a)--)
#define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
#define pb push_back
#define in insert
#define ss second
#define ff first
#define vi vector <int>
#define fa(a, v) for(int (a) : (v))
#define mnel(a) *min_element(all(a))
#define mxel(a) *max_element(all(a))
#define si set<int>
#define sov(a) sort(all((a)))
ve<vi> G, C;
vi num, siz, low;
int n, x;
pii X, Y, Z;
bool found = 0, sol = 0;
tuple<int, int, int> top ,bottom;
vector <bool> B;

void dfs (int u, int p){

    siz[u] = 1;
    x ++;
    num[u] = x;
    low[u] = x;
    bool ok = 1;

    fa(v, G[u]){
        if(num[v] == 0){
            dfs(v, u);
            siz[u] += siz[v];
            low[u] = min(low[v], low[u]);
            if(siz[v] >= X.ff)
                ok = 0;
            C[u].pb(v);
        }
        else
            if(v != p)
                low[u] = min(low[u], num[v]);
    }

    if(siz[u] < X.ff)
        ok = 0;
    if(ok && !found){
        found = 1;
        int cur = siz[u];
        fa(v, C[u]){
            if(low[v] < num[u]){
                if(cur - siz[v] >= X.ff){
                    B[v] = 1;
                    cur -= siz[v];
                }
            }
        }
        int opt = n - cur;
        if(opt >= Y.ff){
            sol = 1;
            top = {Y.ff, Y.ss, p};
            bottom = {X.ff, X.ss, u};
        }
        else
        if(opt >= X.ff){
            sol = 1;
            top = {X.ff, X.ss, p};
            bottom = {Y.ff, Y.ss, u};
        }
    }

}

vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {

    vi ans(n);
    int m = p.size();
    n = nn;
    G = ve<vi> (n);
    C = ve<vi> (n);
    num = vi (n);
    siz = vi (n);
    low = vi (n);
    B = ve<bool> (n);
    queue <int> Q;

    fp(i,0,m){
        G[p[i]].pb(q[i]);
        G[q[i]].pb(p[i]);
    }
    ve<pii> A = {{a, 1}, {b, 2}, {c, 3}};
    sort(all(A));
    X = A[0], Y = A[1], Z = A[2];

    dfs(0, -1);
    if(sol){
        ans = vi (n, Z.ss);
        int sz, d, s;
        tie(sz, d, s) = bottom;
        ans[s] = d;
        sz --;
        Q.push(s);
        while(Q.size()){
            int u = Q.front();
            Q.pop();
            fa(v, C[u]){
                if(!B[v]){
                    if(sz > 0){
                        ans[v] = d;
                        Q.push(v);
                        sz --;
                    }
                }
            }
        }

        tie(sz, d, s) = top;
        ans[s] = d;
        sz--;
        Q.push(s);
        while(Q.size()){
            int u = Q.front();
            Q.pop();
            fa(v, G[u]){
                if(ans[v] == Z.ss){
                    if(sz > 0){
                        sz--;
                        ans[v] = d;
                        Q.push(v);
                    }
                }
            }
        }
    }
    else
        ans = vi (n);
    return ans;
}

Compilation message (stderr)

split.cpp: In function 'void dfs(int, int)':
split.cpp:26:26: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   26 | #define fa(a, v) for(int (a) : (v))
      |                          ^
split.cpp:47:5: note: in expansion of macro 'fa'
   47 |     fa(v, G[u]){
      |     ^~
split.cpp:26:26: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   26 | #define fa(a, v) for(int (a) : (v))
      |                          ^
split.cpp:66:9: note: in expansion of macro 'fa'
   66 |         fa(v, C[u]){
      |         ^~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
      |                           ^
split.cpp:103:5: note: in expansion of macro 'fp'
  103 |     fp(i,0,m){
      |     ^~
split.cpp:26:26: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   26 | #define fa(a, v) for(int (a) : (v))
      |                          ^
split.cpp:122:13: note: in expansion of macro 'fa'
  122 |             fa(v, C[u]){
      |             ^~
split.cpp:26:26: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
   26 | #define fa(a, v) for(int (a) : (v))
      |                          ^
split.cpp:140:13: note: in expansion of macro 'fa'
  140 |             fa(v, G[u]){
      |             ^~

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