제출 #724404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
724404		PixelCat	Split the Attractions (IOI19_split)	C++14	0 / 100	589 ms	1048576 KiB

split

#include "split.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200010;

vector<pii> edge;
vector<int> adj[MAXN];
// vector<int> tr[MAXN];
// int siz[MAXN];
// int vis[MAXN];

// int nbcc;
// vector<int> bcc[MAXN];
// int d[MAXN];
// int lo[MAXN];

// void link_tr(int a, int b) {
//     edge.eb(a, b);
//     tr[a].eb(b);
//     tr[b].eb(a);
// }

// vector<int> st;
// void dfs_ap(int n, int dep) {
//     d[n] = lo[n] = dep;
//     st.eb(n);
//     for(auto &i:adj[n]) {
//         if(d[i]) {
//             lo[n] = min(lo[n], d[i]);
//         } else {
//             dfs_ap(i, dep + 1);
//             lo[n] = min(lo[n], lo[i]);

//             // bcc found
//             if(lo[i] >= d[n]) {
//                 while(st.back() != n) {
//                     bcc[nbcc].eb(st.back());
//                     st.pop_back();
//                 }
//                 bcc[nbcc].eb(n);
//                 nbcc++;
//             }
//         }
//     }
// }

// int dfs_siz(int n, int p, int N) {
//     siz[n] = (n < N);
//     for(auto &i:tr[n]) if(i != p) {
//         siz[n] += dfs_siz(i, n, N);
//     }
//     // cerr << n << " = " << siz[n] << "\n";
//     return siz[n];
// }

// vector<int> comp(int n, int ban, int cnt, int N) {
//     memset(vis, 0, sizeof(vis));
//     // vis[ban] = 1; vis[n] = 1;
//     if(n < N) { // n is ap, ban is bcc
//         int bid = ban - N;
//         for(auto &i:bcc[bid]) vis[i] = 1;
//     } else { // ban is ap, n is bcc
//         int bid = n - N;
//         for(auto &i:bcc[bid]) if(i != ban) {
//             n = i; break;
//         }
//         vis[ban] = 1; vis[n] = 1;
//     }

//     queue<int> que;
//     que.emplace(n);
//     vector<int> res;
//     while(!que.empty()) {
//         int cur = que.front(); que.pop();
//         res.eb(cur);
//         cnt--;
//         if(cnt == 0) return res;
        
//         for(auto &i:adj[cur]) if(!vis[i]) {
//             vis[i] = 1;
//             que.emplace(i);
//         }
//     }
//     assert(false);
//     return res;
// }

vector<int> ord;
void dfs(int n, int p) {
    ord.eb(n);
    for(auto &i:adj[n]) if(i != p) {
        dfs(i, n);
    }
}

vector<int32_t> find_split(int32_t n, int32_t a, int32_t b, int32_t c, vector<int32_t> p, vector<int32_t> q) {
    // int x, y;
    // int ix, iy;
    // {
    //     vector<pii> ord = {{a, 1}, {b, 2}, {c, 3}};
    //     sort(all(ord));
    //     x = ord[0].F; ix = ord[0].S;
    //     y = ord[1].F; iy = ord[1].S;
    // }

    int m = sz(p);
    // assert(m == n - 1);
    For(i, 0, m - 1) {
        int s = p[i];
        int t = q[i];
        adj[s].eb(t);
        adj[t].eb(s);
    }

    int p0 = -1;
    For(i, 0, n - 1) if(sz(adj[i]) == 1) {
        p0 = i;
    }
    dfs(p0, p0);
    vector<int> res(n);
    For(i, 0, n - 1) {
        int id = ord[i];
        if(i < a) res[id] = 1;
        else if(i < a + b) res[id] = 2;
        else res[id] = 3;
    }
    return res;

    // nbcc = 0;
    // dfs_ap(0, 1);
    // For(i, 0, nbcc - 1) {
    //     // cerr << sz(bcc[i]) << ":";
    //     for(auto &j:bcc[i]) {
    //         // cerr << " " << j;
    //         link_tr(n + i, j);
    //     }
    //     // cerr << "\n";
    // }
    // // return vector<int>(n, 0);

    // dfs_siz(0, -1, n);
    // for(auto &e:edge) {
    //     int s = e.F;
    //     int t = e.S;
    //     if(siz[s] < siz[t]) swap(s, t);
    //     // s is parent
    //     int s1 = siz[t];
    //     int s2 = n - s1;
    //     if(s1 > s2) {
    //         swap(s1, s2);
    //         swap(s, t);
    //     }
    //     // size of t's side is smaller (s1)
    //     if(s1 >= x && s2 >= y) {
    //         // cerr << "! " << s << " " << t << "\n";
    //         vector<int> v1 = comp(t, s, x, n);
    //         vector<int> v2 = comp(s, t, y, n);

    //         vector<int> res(n, 6 - ix - iy);
    //         for(auto &i:v1) res[i] = ix;
    //         for(auto &i:v2) res[i] = iy;
    //         return res;
    //     }
    // }
    // return vector<int>(n, 0);
}

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