Submission #925017

#	Time	Username	Problem	Language	Result	Execution time	Memory
925017		hmm789	Split the Attractions (IOI19_split)	C++14	40 / 100	72 ms	24376 KiB

split

#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000000000000
#define MOD 998244353

vector<int> adj[100000], grpv[100000];
set<pair<int, tuple<int, int, int>>> adj2[100000];
vector<int> path, res;
vector<pair<int, int>> t1;
int sz[100000], grp[100000], d, e, c1 = -1, c2 = -1, cnt;
bool v[100000];

int size(int x, int g) {
    v[x] = 1; sz[x] = 1; grp[x] = g;
    if(g != -1) grpv[g].push_back(x);
    for(int i : adj[x]) if(!v[i]) {
        if(g == -1) sz[x] += size(i, i);
        else sz[x] += size(i, g);
    }
    return sz[x];
}

int centroid(int x, int n) {
    v[x] = 1;
    for(int i : adj[x]) if(!v[i] && sz[i] > n/2) return centroid(i, n);
    return x;
}

bool dfs(int x, int sz, int _c1, int _c2) {
    v[x] = 1;
    if(sz >= d) {
        c1 = _c1; c2 = _c2;
        path.push_back(x);
        return true;
    }
    for(auto i : adj2[x]) if(!v[i.first]) {
        if(dfs(i.first, sz+get<0>(i.second), get<1>(i.second), get<2>(i.second))) {
            path.push_back(x);
            return true;
        }
    }
    return false;
}

void dfs2(int x) {
    v[x] = 1;
    if(cnt == 0) return;
    res[x] = t1[0].second;
    cnt--;
    for(int i : adj[x]) if(!v[i] && grp[i] == grp[x]) dfs2(i);
}

void dfs3(int x) {
    if(cnt == 0) return;
    res[x] = t1[1].second;
    cnt--;
    for(int i : adj[x]) if(res[i] == 0) dfs3(i);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    for(int i = 0; i < n; i++) res.push_back(0);
    for(int i = 0; i < p.size(); i++) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }
    t1 = {{a, 1}, {b, 2}, {c, 3}};
    sort(t1.begin(), t1.end());
    d = t1[0].first; e = t1[1].first;
    size(0, -1);
    memset(v, 0, sizeof(v));
    int cen = centroid(0, n);
    memset(v, 0, sizeof(v));
    size(cen, -1);
    for(int i : adj[cen]) if(sz[i] >= d) {
        memset(v, 0, sizeof(v));
        cnt = d;
        dfs2(i);
        cnt = e;
        dfs3(cen);
        for(int j = 0; j < n; j++) if(res[j] == 0) res[j] = t1[2].second;
        return res;
    }
    for(int i = 0; i < n; i++) {
        for(int j : adj[i]) {
            if(grp[i] == -1 || grp[j] == -1) continue;
            if(grp[i] == grp[j]) continue;
            auto it = adj2[grp[i]].lower_bound({grp[j], {0, 0, 0}});
            if(it != adj2[grp[i]].end() && it->first == grp[j]) continue;
            adj2[grp[i]].insert({grp[j], {sz[grp[j]], i, j}});
            adj2[grp[j]].insert({grp[i], {sz[grp[i]], j, i}});
        }
    }
    memset(v, 0, sizeof(v));
    for(int i : adj[cen]) if(!v[i]) {
        if(dfs(i, sz[i], -1, -1)) break;
    }
    if(c1 == -1) return res;
    cnt = d;
    for(int i = 1; i < path.size(); i++) {
        for(int j : grpv[path[i]]) {
            res[j] = t1[0].second;
            cnt--;
        }
    }
    memset(v, 0, sizeof(v));
    dfs2(c2);
    cnt = e;
    dfs3(cen);
    for(int i = 0; i < n; i++) if(res[i] == 0) res[i] = t1[2].second;
    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:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < p.size(); i++) {
      |                    ~~^~~~~~~~~~
split.cpp:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i = 1; i < path.size(); i++) {
      |                    ~~^~~~~~~~~~~~~

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