Submission #597305

#	Time	Username	Problem	Language	Result	Execution time	Memory
597305		keta_tsimakuridze	Split the Attractions (IOI19_split)	C++14	100 / 100	159 ms	30284 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
const int N = 1e5 + 5;
int sz[N], f[N], p[N], bl[N], h[N];
vector<int> V[N], adj[N], eb[N];
vector<int> ans, b(4);
vector<pii> x;
void dfs(int u, int P) {
    f[u] = 1;
    p[u] = P;
    h[u] = h[P] + 1;
    for(int i = 0; i < V[u].size(); i++) {
        if(f[V[u][i]]) {
            eb[u].push_back(V[u][i]);
            continue;
        }
        dfs(V[u][i], u);
        adj[u].push_back(V[u][i]);
        sz[u] += sz[V[u][i]];
    }
    ++sz[u];
}
void dfs2(int u, int P) {
    int F = 0;
    for(int i = 0; i < eb[u].size();i++) {
        if(h[eb[u][i]] < h[P]) {
            F = 1;
            x.push_back({u, sz[u]});
            break;
        }
    }
    if(F) return;
    for(int i = 0; i < adj[u].size(); i++) {
        dfs2(adj[u][i], P);
    }
}
void dfs3(int u, int t) {
    if(!b[t]) return;
    --b[t];
    ans[u] = t;
    f[u] = 1;
    for(int i = 0; i < adj[u].size(); i++) {
        if(bl[adj[u][i]]) continue;
        if(!b[t]) return;
        dfs3(adj[u][i], t);
    }
}
void dfs4(int u, int t) {
    if(!b[t]) return;
    --b[t];
    ans[u] = t;
    f[u] = 1;
    for(int i = 0; i < V[u].size(); i++) {
        if(f[V[u][i]]) continue;
        if(!b[t]) return;
        dfs4(V[u][i], t);
    }
}
int get(vector<int> x, int t) {
    pii mn;
    mn = {N, 5};
    for(int i = 1; i <= 3; i++) {
        if(i == t) continue;
        mn = min(mn, {x[i], i});
    }
    return mn.s;
}
vector<int> find_split(int n, int A, int B, int C, vector<int> P, vector<int> q) {
	ans.resize(n);
	int a = min(A, min(B, C));
	b[1] = A, b[2] = B, b[3] = C;//cout << "+" << endl;
	for(int i = 0; i < P.size(); i++) {
        int u = P[i], v = q[i];
        V[u].push_back(v);
        V[v].push_back(u);
	}
	dfs(0, 0);

	for(int i = 0; i < n; i++) {
        if(sz[i] < a) continue;
        int F = 0;
        for(int j = 0; j < adj[i].size(); j++) {
            if(sz[adj[i][j]] >= a) {
                F = 1;
                break;
            }
        }
        if(F) continue;
        if(!i) return ans;
        x.clear();
        for(int j = 0; j < adj[i].size(); j++) {
            dfs2(adj[i][j], i);
        }
        int oth = n - sz[i];
        while(oth < a) {
            if(!x.size()) break;
            oth += x.back().s;
            bl[x.back().f] = 1;
            x.pop_back();
        }
        if(oth < a) return ans;

        int t1 = get(b, 0), t2 = get(b, t1);
        for(int j = 0; j < n; j++) f[j] = 0;
        int bbb = b[t2];
        dfs3(i, (oth >= bbb ? t1 : t2));

        dfs4(p[i], (oth < bbb ? t1 : t2)); assert(!b[t2]&&!b[t1]);
        for(int j = 0; j < n; j++) if(!ans[j]) ans[j] = 6 - t1 - t2;
        return ans;
	}
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'void dfs(int, int)':
split.cpp:16:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
split.cpp: In function 'void dfs2(int, int)':
split.cpp:29:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0; i < eb[u].size();i++) {
      |                    ~~^~~~~~~~~~~~~~
split.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0; i < adj[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
split.cpp: In function 'void dfs3(int, int)':
split.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0; i < adj[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
split.cpp: In function 'void dfs4(int, int)':
split.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i = 0; i < V[u].size(); i++) {
      |                    ~~^~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 0; i < P.size(); i++) {
      |                 ~~^~~~~~~~~~
split.cpp:86:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(int j = 0; j < adj[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~
split.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int j = 0; j < adj[i].size(); j++) {
      |                        ~~^~~~~~~~~~~~~~~

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