Submission #288615

#	Time	Username	Problem	Language	Result	Execution time	Memory
288615		Mercenary	Split the Attractions (IOI19_split)	C++14	100 / 100	202 ms	22732 KiB

split

#include "split.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

int A , B;
int sub[maxn];

vector<int> canpick;
vector<int> adj[maxn] , adj1[maxn];
int root = -1;
void dfs(int u){
    sub[u] = 1;
    bool ok = 0;
    for(auto & c : adj[u]){
        if(sub[c] == -1){
            adj1[u].pb(c);
            dfs(c);
            sub[u] += sub[c];
            ok |= sub[c] >= A;
        }
    }
    if(ok == 0 && sub[u] >= A)root = u;
}

void dfs1(int u){
    bool ok = 0;
    for(auto & c : adj[u]){
        if(sub[c] > sub[root])ok = 1;
    }
    if(u != root && ok){
        canpick.pb(u);
        return;
    }
    for(auto & c : adj1[u]){
        dfs1(c);
    }
}

bool cut[maxn];

bool vis[maxn];
vector<int> valA , valB;

void dfs2(int u){
    valA.pb(u);
    vis[u] = 1;
    for(auto & c : adj1[u]){
        if(cut[c])continue;
        dfs2(c);
    }
}

void dfs3(int u){
    valB.pb(u);
    vis[u] = 1;
    for(auto &c : adj[u]){
        if(vis[c] == 1)continue;
        dfs3(c);
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    for(int i = 0 ; i < p.size() ; ++i){
        adj[p[i]].pb(q[i]);
        adj[q[i]].pb(p[i]);
    }
    A = min({a , b , c});
    memset(sub,-1,sizeof sub);
    dfs(0);
    dfs1(root);
    for(auto & c : canpick){
        if(sub[root] - sub[c] < A)break;
        sub[root] -= sub[c];
        cut[c] = 1;
    }
    dfs2(root);
    for(int i = 0 ; i < n ; ++i){
        if(vis[i] == 0){
            dfs3(i);
            break;
        }
    }
    if(valA.size() > valB.size())swap(valA,valB);
    vector<ii> val = {mp(a,1),mp(b,2),mp(c,3)};
    sort(val.begin(),val.end());
    if(val[0].first <= valA.size() && val[1].first <= valB.size()){
        vector<int> res(n , val[2].second);
        for(int i = 0 ; i < val[0].first ; ++i){
            res[valA[i]] = val[0].second;
        }
        for(int i = 0 ; i < val[1].first ; ++i){
            res[valB[i]] = val[1].second;
        }
        return res;
    }
    return vector<int>(n , 0);
}

#ifdef LOCAL
#include "split.h"
#include <cstdio>
#include <cassert>

using namespace std;

int main() {
    freopen("A.INP","r",stdin);
	int n, m, a, b, c;
	assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
	vector<int> p(m), q(m);
	for (int i=0; i<m; i++)
		assert(2 == scanf("%d%d", &p[i], &q[i]));
	fclose(stdin);

	vector<int> result = find_split(n, a, b, c, p, q);

	for (int i=0; i<(int)result.size(); i++)
		printf("%s%d", ((i>0)?" ":""), result[i]);
	printf("\n");
	fclose(stdout);
	return 0;
}

#endif // LOCAL

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0 ; i < p.size() ; ++i){
      |                     ~~^~~~~~~~~~
split.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     if(val[0].first <= valA.size() && val[1].first <= valB.size()){
split.cpp:102:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     if(val[0].first <= valA.size() && val[1].first <= valB.size()){

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