Submission #528554

#	Time	Username	Problem	Language	Result	Execution time	Memory
528554		jenny00513	Split the Attractions (IOI19_split)	C++17	Compilation error	0 ms	0 KiB

split

#include "bits/stdc++.h"
#include "split.h"
using namespace std;
 
#define F first
#define S second
#define rep(i, n) for (int i = 1; i <= n; i++)
#define all(x) (x).begin(), (x).end()
#define comp(x) sort(all((x))); (x).erase(unique(all((x))), (x).end())
#define sz(x) (int)((x).size())
#define sq(x) (x) * (x)
#define srt(x) sort(all(x))
#define pb push_back
#define eb emplace_back
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
 
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define imp cout << "-1\n"
#define el cout << "\n"
 
const int MAX = 1e5 + 5;
const int LOG = 20;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;
const int dy[8] = { -1, 0, 1, 0, -1, 1, 1, -1 };
const int dx[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };
 
template<typename ...Args>
void read(Args&... args) { (cin >> ... >> args); }
 
class DisjointSet {
public:
    
    DisjointSet(int n): n(n), par(n + 5), s(n + 5) {
        init();
    }
    int n; vector<int> par, s;
    
    void init(void)
    {
        iota(all(par), 0);
        fill(all(s), 1);
    }
    
    int Find(int x)
    {
        if (x == par[x]) return x;
        return par[x] = Find(par[x]);
    }
    
    bool Union(int p, int q)
    {
        p = Find(p); q = Find(q); if (p == q) return false;
        par[q] = p; s[p] += s[q]; s[q] = 0; return true;
    }
    
    bool same(int p, int q)
    {
        p = Find(p); q = Find(q);
        return (p == q);
    }
};
 
vi vc[MAX], adj[MAX], szz(MAX);
vector<bool> vst(MAX);
 
int getSize(int node, int par)
{
    szz[node] = 1;
 
    for (auto &each : vc[node])
    {
        if (each == par) continue;
        szz[node] += getSize(each, node);
    }
 
    return szz[node];
}
 
int getCent(int node, int par, int half)
{
    for (auto &each : vc[node])
    {
        if (each == par) continue;
        if (szz[each] > half) return getCent(each, node, half);
    }
 
    return node;
}
 
vi path;
 
int getComp(int node, int par)
{
    int cnt = 1;
    path.pb(node);
 
    for (auto &each : vc[node])
    {
        if (each == par) continue;
        cnt += getComp(each, node);
    }
 
    return cnt;
}

int cnt;
bool chk[MAX];
vector<pi> s(3);
vi ans(n);

void dfs1(int node)
{
    chk[node] = true;
    cnt--; ans[node] = s[0].S;
    
    if (cnt <= 0) return;

    for (auto &each : vc[node])
    {
        if (chk[each]) continue;
        dfs1(each);
    }
}

void dfs2(int node)
{
    cnt--; ans[node] = s[1].S;
    if (cnt <= 0) return;

    for (auto &each : vc[node])
    {
        if (ans[each]) continue;
        dfs2(each);
    }
}

vector<int> find_split(int N, int A, int B, int C, vector<int> P, vector<int> Q) {
	
    int n, m; 
    
    n = N;
    s[0].F = A; s[1].F = B; s[2].F = C;
    m = sz(P);
 
    for (int i = 0; i < 3; i++) s[i].S = i + 1;
    
    srt(s);
 
    vector<pi> edge;
    DisjointSet ds(n);
 
    for (int i = 0; i < m; i++)
    {
        int u, v; u = P[i]; v = Q[i];
        edge.eb(u, v);
    }

    vector<pi> more, st;
 
    for (auto &[u, v] : edge)
    {
        if (ds.same(u, v)) 
        {
            more.pb(make_pair(u, v));
            continue;
        }

        ds.Union(u, v);
        vc[u].pb(v); vc[v].pb(u);
        st.eb(u, v);
    }
 
    int limit = getSize(0, -1) / 2;
    int cent = getCent(0, -1, limit);

    DisjointSet dss(n);

    int fnode = -1;

    for (auto &[u, v] : st)
    {
        if (u == cent || v == cent) continue;
        dss.Union(u, v);
    }

    // vc: spanning tree
    // adj: spanning tree without centroid
    // st: spanning tree's edges
 
    for (auto &node : vc[cent])
    {
        if (node == cent) continue;

        int tmp = dss.s[dss.Find(node)];//getComp(node, cent);
 
        if (tmp >= s[0].F)
        {
            fnode = node;
            break;/*
            for (int i = 0; i < s[0].F; i++) ans[path[i]] = s[0].S;
            
            path.clear();
            tmp = getComp(cent, node);
 
            for (int i = 0; i < s[1].F; i++) ans[path[i]] = s[1].S;
            for (int i = 0; i < n; i++) if (!ans[i]) ans[i] = s[2].S;
 
            return ans;*/
        }
    }

    if (fnode == -1)
    {
        for (int i = 0; i < sz(more); i++)
        {
            int u = more[i].F, v = more[i].S;
            if (u == cent || v == cent) continue;
            dss.Union(u, v);
            if (dss.s[dss.Find(u)] >= s[0].F)
            {
                fnode = u;
                break;
            }
        }
    }

    if (fnode == -1) return ans;
 
    cnt = s[0].F;
    vst[cent] = true;
    dfs1(fnode);

    cnt = s[1].F;
    dfs2(cent);

    for (int i = 0; i < n; i++) if (ans[i] == 0) ans[i] = s[2].S;

    return ans;
}

Compilation message (stderr)

split.cpp:117:8: error: 'n' was not declared in this scope
  117 | vi ans(n);
      |        ^