Submission #540852

#	Time	Username	Problem	Language	Result	Execution time	Memory
540852		Vladth11	Split the Attractions (IOI19_split)	C++14	100 / 100	142 ms	27284 KiB

split

#include <bits/stdc++.h>
#include "split.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
 
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;
 
const ll NMAX = 100001;
const ll VMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 1000000;
const ll nr_of_bits = 16;
 
vector <int> sol;
vector <int> v[NMAX], tree[NMAX], nou[NMAX];
int lvl[NMAX];
int sz[NMAX];
 
void DFS(int node) {
    for(auto x : v[node]) {
        if(lvl[x])
            continue;
        tree[node].push_back(x);
        tree[x].push_back(node);
        lvl[x] = lvl[node] + 1;
        DFS(x);
    }
}
 
int total = 0;
 
void getsz(int node, int p) {
    sz[node] = 1;
    for(auto x : tree[node]) {
        if(x == p)
            continue;
        getsz(x, node);
        sz[node] += sz[x];
    }
    total = sz[node];
}
 
int root;
vector <int> sons[NMAX];
int cc;
int cnt[NMAX];
 
int findCentroid(int node, int p) {
    for(auto x : tree[node]) {
        if(x == p)
            continue;
        if(sz[x] > total / 2)
            return findCentroid(x, node);
    }
    return node;
}
 
int comp[NMAX];
 
void baga(int node, int p) {
    comp[node] = cc;
    cnt[cc]++;
    for(auto x : tree[node]) {
        if(x == p)
            continue;
        baga(x, node);
    }
}
 
 
int col[4];
int cate;
 
void marcheaza(int node, int p, int cul) {
    if(cate == 0)
        return;
    sol[node] = cul;
    cate--;
    for(auto x : tree[node]) {
        if(x == p || sol[x] != 0)
            continue;
        marcheaza(x, node, cul);
    }
}
 
int viz[NMAX];
vector <int> cine;
 
void greedy(int node) {
    viz[node] = 1;
    if(cate <= 0)
        return;
    cate -= cnt[node];
    cine.push_back(node);
    for(auto x : nou[node]) {
        if(viz[x])
            continue;
        greedy(x);
    }
}
 
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    col[0] = 1;
    col[1] = 2;
    col[2] = 3;
    sol.resize(n);
    if(a > b) {
        swap(a, b);
        swap(col[0], col[1]);
    }
    if(b > c) {
        swap(c, b);
        swap(col[2], col[1]);
    }
    if(a > b) {
        swap(a, b);
        swap(col[0], col[1]);
    }
    for(int i = 0; i < p.size(); i++) {
        int a = p[i];
        int b = q[i];
        v[a].push_back(b);
        v[b].push_back(a);
    }
    lvl[0] = 1;
    DFS(0);
    getsz(0, -1);
    root = findCentroid(0, -1);
 
    for(auto x : tree[root]) {
        cc = x; /// Componenta poarta numele celui mai inalt din ea (reprezentantul e fiu a root-ului)
        baga(x, root);
    }
 
    getsz(root, -1);
    int maxim = -1;
    for(auto x : tree[root]) {
        if(maxim == -1 || sz[maxim] < sz[x])
            maxim = x;
    }
 
    if(sz[maxim] >= a) {
        cate = a;
        marcheaza(maxim, root, col[0]);
        cate = b;
        marcheaza(root, -1, col[1]);
        for(int i = 0; i < n; i++) {
            if(sol[i] == 0)
                sol[i] = col[2];
        }
        return sol;
    }
    int cnv = -1;
    for(int i = 0; i < n; i++) {
        if(i == root)
            continue;
        for(auto x : v[i]) {
            if(x == root)
                continue;
            if(abs(lvl[i] - lvl[x]) == 1)
                continue;
            nou[comp[i]].push_back(comp[x]);
        }
    }
    cate = a;
    viz[root] = 1;
    for(int i = 0; i < n; i++){
        cate = a;
        if(!viz[comp[i]]){
            greedy(comp[i]);
            if(cate <= 0)
                break;
        }   
      	cine.clear();
    }
  	cate = a;
    for(auto x : cine) {
        marcheaza(x, root, col[0]);
    }
    if(cate > 0){
        for(int i = 0; i < n; i++){
            sol[i] = 0;
        }
        return sol;
    }
    cate = b;
    marcheaza(root, -1, col[1]);
    for(int i = 0; i < n; i++) {
        if(sol[i] == 0)
            sol[i] = col[2];
    }
    return sol;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:123:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i = 0; i < p.size(); i++) {
      |                    ~~^~~~~~~~~~
split.cpp:157:9: warning: unused variable 'cnv' [-Wunused-variable]
  157 |     int cnv = -1;
      |         ^~~

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