Submission #1011693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011693		u_suck_o	Split the Attractions (IOI19_split)	C++17	40 / 100	58 ms	26320 KiB

split

#include "bits/stdc++.h"
#include "split.h"
#define MAXN 200005

using namespace std;

int N;
bool vis[MAXN], vis1[MAXN];
int sz[MAXN], color[MAXN];
vector<int> adj[MAXN];
vector<int> nadj[MAXN];
vector<pair<int, int>> v;
bool found = false;
int cnt, q;

void ass1(int node, int num, int par) {
    if (cnt >= q)
        return;
    color[node] = num;
    cnt++;
    vis1[node] = true;
    for (int j : nadj[node]) {
        if (j != par && !vis1[j])
            ass1(j, num, node);
    }
}

void ass2(int node, int num, int par) {
    if (cnt >= q)
        return;
    color[node] = num;
    cnt++;
    vis1[node] = true;
    for (int j : adj[node]) {
        if (j != par && !vis1[j])
            ass2(j, num, node);
    }
}

void dfs(int node, int par) {
    if (found)
        return;
    if (par != -1) {
        nadj[par].push_back(node);
        nadj[node].push_back(par);
    }
    sz[node] = 1;
    vis[node] = true;
    for (int j : adj[node]) {
        if (!vis[j]) {
            dfs(j, node);
            if (found)
                return;
            sz[node] += sz[j];
        }
    }
    if (found)
        return;
    if (sz[node] >= v[0].first && N-sz[node] >= v[1].first) {
        found = true;
        cnt = 0; q = v[0].first;
        ass1(node, v[0].second, par);
        
        cnt = 0; q = v[1].first;
        ass2(par, v[1].second, node);
    } else if (sz[node] >= v[1].first && N-sz[node] >= v[0].first) {
        found = true;
        cnt = 0; q = v[1].first;
        ass1(node, v[1].second, par);
        
        cnt = 0; q = v[0].first;
        ass2(par, v[0].second, node);
    }
}


vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    N = n;
    v.push_back({a, 1});
    v.push_back({b, 2});
    v.push_back({c, 3});
    sort(v.begin(), v.end());
    
    vector<int> res;
    for (int i = 0; i < p.size(); i++) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }
    /*for (int i = 0; i < n; i++) {
        if (!found) {
            memset(vis, 0, sizeof vis);
            memset(sz, 0, sizeof sz);
            dfs(i, -1);
        }
    }*/
    
    memset(vis, 0, sizeof vis);
    memset(sz, 0, sizeof sz);
    dfs(0, -1);
    
    if (!found)
        return vector<int>(n, 0);
    
    for (int i = 0; i < n; i++) {
        if (color[i] == 0)
            res.push_back(v[2].second);
        else
            res.push_back(color[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:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0; i < p.size(); i++) {
      |                     ~~^~~~~~~~~~

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