Submission #291383

#	Time	Username	Problem	Language	Result	Execution time	Memory
291383		Dremix10	Split the Attractions (IOI19_split)	C++17	22 / 100	652 ms	1048580 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x)
    #define p2(x,y)
    #define pp(x)
    #define pv(x)
    #define ppv(x)
#endif
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 1e18;
const int MOD = 1e9+7;
const int N = 2e5+1;

vector<vector<int> > adj(N);
vector<int> res;
bool v[N];
pi siz[3];
int cnt[N];
int par[N];

void dfs(int s, int e){
    par[s] = e;
    cnt[s] = 1;
    for(auto x : adj[s])
        if(x!=e && res[x]==0){
            dfs(x,s);
            cnt[s] += cnt[x];
        }
}

int curr;
int now;

void color(int s, int e){
    p2(s,e)
    pp(siz[curr-1])
    p(now)
    if(now+1>siz[curr-1].F)return;
    res[s] = siz[curr-1].S;
    now++;
    p2(s,now)
    for(auto x : adj[s])
        if(x!=e && res[x]==0){
            color(x,s);
        }
}

int lim;

void solve(int s, int e){
    for(auto x : adj[s])
        if(x!=e && cnt[x]>=siz[curr-1].F && res[x]==0){
            solve(x,s);
            if(curr==lim)return;
        }
    if(cnt[s] >= siz[curr-1].F){
        res[s] = siz[curr-1].S;
        now = 1;
        for(auto x : adj[s])
            if(x!=e)
            color(x,s);
        curr++;
    }
}



vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    siz[0] = {a,1};
    siz[1] = {b,2};
    siz[2] = {c,3};
    sort(siz,siz+3);
    //swap(siz[0],siz[1]);
	int i;
	for(i=0;i<p.size();i++){
        int x = p[i],y = q[i];
        adj[x].push_back(y);
        adj[y].push_back(x);
	}
	res.assign(n,0);
	dfs(0,0);

    int start,col,los=MOD;
    int j;
    for(i=0;i<n;i++){
        for(j=0;j<3;j++){
            if(cnt[i] < siz[j].F)continue;
            int waste = cnt[i] - siz[j].F;
            //p2(cnt[i],siz[j].F)
            //p2(i,j)
            if(waste < los){
                los = waste;
                start = i;
                col = j;
            }
        }
    }
    p2(start,col)

    set<int> cols;
    for(i=1;i<=3;i++)cols.insert(i);
    curr = col+1;
    p2(los,curr)

    now = 0;
    p(par[start])
    pp(siz[curr-1])
    color(start,par[start]);
    cols.erase(curr);
    pv(cols)
    pv(res)
    curr = *cols.begin();
    int need = siz[curr-1].F;

    p2(curr,need)
    if(res[0] || need > n - cnt[start]){
        for(auto &x : res)
            x = 0;
        return res;
    }

    now = 0;
    color(0,0);
    cols.erase(curr);
    pv(res)
    curr = *cols.begin();
    for(auto &x : res)
        if(x==0)x = siz[curr-1].S;
    return res;


}

/*
11 10
3 4 4
0 1
1 3
1 4
1 5
4 6
0 2
2 7
2 8
7 9
9 10

g++ grader.cpp split3.cpp -Ddremix
*/

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:94:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for(i=0;i<p.size();i++){
      |          ~^~~~~~~~~
split.cpp:121:15: warning: 'col' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |     curr = col+1;
      |            ~~~^~
split.cpp:127:10: warning: 'start' may be used uninitialized in this function [-Wmaybe-uninitialized]
  127 |     color(start,par[start]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

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