Submission #392015

#	Time	Username	Problem	Language	Result	Execution time	Memory
392015		Sorting	Split the Attractions (IOI19_split)	C++17	40 / 100	184 ms	16792 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 3;

int n, a, b, c, sz[N], d[N], root;
int num_a, num_b, num_c;
vector<int> adj[N];
bool vis[N];
vector<int> ans;
clock_t timer = clock();

int add_not_subtree(int u, int forbidden, int cnt, int val){
    //cout << "add_not_subtree " << u << " " << forbidden << " " << cnt << " " << val << endl;
    if(!cnt) return 0;
    ans[u] = val;
    --cnt;
    for(int to: adj[u])
        if(to != forbidden && d[to] == d[u] + 1)
            cnt = add_not_subtree(to, forbidden, cnt, val);
    return cnt;
}

int add_subtree(int u, int cnt, int val){
    //cout << "add_subtree " << u << " " << cnt << " " << val << endl;
    if(!cnt) return 0;
    ans[u] = val;
    --cnt;
    for(int to: adj[u])
        if(d[to] == d[u] + 1)
            cnt = add_subtree(to, cnt, val);
    return cnt;
}

void d_dfs(int u){
    sz[u] = 1;
    vis[u] = true;
    for(int to: adj[u])
        if(!vis[to]){
            d[to] = d[u] + 1;
            d_dfs(to);
            sz[u] += sz[to];
        }
}

bool dfs(int u){
    bool bigger = false;
    for(int to: adj[u])
        if(d[to] == d[u] + 1){
            if(dfs(to)) return true;
            if(sz[to] >= a) bigger = true;
            if(bigger) break;
        }
    if(!bigger && sz[u] >= a){
        if(n - sz[u] >= a){
            if(sz[u] <= n - sz[u]){
                add_subtree(u, a, num_a);
                add_not_subtree(root, u, b, num_b);
                for(int i = 0; i < n; ++i)
                    if(!ans[i])
                        ans[i] = num_c;
            }
            else{
                add_subtree(u, b, num_b);
                add_not_subtree(root, u, a, num_a);
                for(int i = 0; i < n; ++i)
                    if(!ans[i])
                        ans[i] = num_c;
            }
            return true;
        }
        else return false;
    }
    return false;
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
	n = _n, a = _a, b = _b, c = _c;
    num_a = 1, num_b = 2, num_c = 3;
    for(int i = 0; i < p.size(); ++i){
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }

    if(a > b) swap(a, b), swap(num_a, num_b);
    if(a > c) swap(a, c), swap(num_a, num_c);
    if(b > c) swap(b, c), swap(num_b, num_c);

    
    mt19937 mt(7);
    ans.resize(n, 0);
    while(((float)clock() - (float)timer) / (float)CLOCKS_PER_SEC <= 1.8){
        root = mt() % n;
        d[root] = 0;
        for(int j = 0; j < n; ++j)
            random_shuffle(adj[j].begin(), adj[j].end(), [&](int mod){
                return mt() % mod;
            });
        fill(ans.begin(), ans.end(), 0);
        fill(vis, vis + n, 0);
        d_dfs(root);
        if(dfs(root)) return ans;
        return ans;
    }
    return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     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