Submission #615839

#	Time	Username	Problem	Language	Result	Execution time	Memory
615839		2fat2code	Split the Attractions (IOI19_split)	C++17	18 / 100	967 ms	146848 KiB

split

#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
//#define int long long
#define rc(s) return cout << s, 0
using namespace std;

const int nmax = 100005;

int N, M, A, B, C, sz[nmax], centroid, indx1, indx2, indx3, nrcomponente, apartinere[nmax];
vector<int> res, nod[nmax], nod_MST[nmax], O_o, componente[nmax], nod3[nmax];
bitset<nmax>viz;

void dfs(int s){
    viz[s] = 1; sz[s] = 1;
    for(auto it : nod[s]){
        if(!viz[it]){
            nod_MST[s].push_back(it);
            nod_MST[it].push_back(s);
            dfs(it);
            sz[s] += sz[it];
        }
    }
}

void dfs2(int s){
    viz[s] = 1; sz[s] = 1;
    for(auto it : nod_MST[s]){
        if(!viz[it]){
            dfs2(it);
            sz[s] += sz[it];
        }
    }
}

int findcentroid(int s, int par = 0){
    for(auto it : nod_MST[s]){
        if(it != par && sz[it] > (N / 2)){
            return findcentroid(it, s);
        }
    }
    return s;
}

void dfs_vanilla(int s, int par, int cock){
    if(A == 0) return;
    else{
        res[s - 1] = cock;
        A--;
        for(auto it : nod_MST[s]){
            if(it != par && !res[it - 1]) dfs_vanilla(it, s, cock);
        }
    }
}

void construct(int it){
    dfs_vanilla(it, centroid, indx1);
    A = B;
    dfs_vanilla(centroid, 0, indx2);
    for(int i=0;i<N;i++){
        if(!res[i]){
            res[i] = indx3;
        }
    }
}

void dfs_timur(int s, int par = 0){
    componente[nrcomponente].push_back(s);
    apartinere[s] = nrcomponente;
    for(auto it : nod_MST[s]){
        if(it != par) dfs_timur(it, s);
    }
}

void dfs_finala(int s){
    viz[s] = 1;
    for(auto it : componente[s]){
        O_o.push_back(it);
    }
    for(auto it : nod3[s]){
        if(!viz[it] && O_o.size() < A) dfs_finala(it);
    }
}

void dfs_slavic(int s, int par = 0){
    if(!B){
        return;
    }
    else{
        --B;
        res[s - 1] = indx2;
        for(auto it : nod_MST[s]){
            if(it != par && !viz[it]) dfs_slavic(it, s);
        }
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	N = n; M = p.size();
	for(auto &it : p){
        ++it;
	}
	for(auto &it : q){
        ++it;
	}
	vector<pair<int,int>>tz; tz.push_back({a, 1}); tz.push_back({b, 2}); tz.push_back({c, 3});
	sort(all(tz));
	A = tz[0].fr; B = tz[1].fr; C = tz[2].fr;
	indx1 = tz[0].sc, indx2 = tz[1].sc, indx3 = tz[2].sc;
	res.resize(N);
	for(int i=0;i<M;i++){
        nod[p[i]].push_back(q[i]);
        nod[q[i]].push_back(p[i]);
	}
	dfs(1);
	centroid = findcentroid(1);
	viz.reset();
	for(int i=1;i<=n;i++) sz[i] = 0;
	dfs2(centroid);
	for(auto it : nod_MST[centroid]){
        if(sz[it] >= A){
            construct(it);
            return res;
        }
	}
	viz.reset();
	for(auto it : nod_MST[centroid]){
        ++nrcomponente;
        dfs_timur(it);
	}
	for(int i=1;i<=n;i++){
        for(auto it : nod[i]){
            if(i != centroid && it != centroid && apartinere[i] != apartinere[it]){
                nod3[i].push_back(it);
                nod3[it].push_back(i);
            }
        }
	}
	for(int i=1;i<=nrcomponente;i++){
        if(!viz[i]){
            O_o.clear();
            dfs_finala(i);
            if(O_o.size() >= A){
                for(int i=0;i<A;i++) res[O_o[i] - 1] = indx1;
                viz.reset();
                for(auto it : O_o) viz[it] = 1;
                dfs_slavic(centroid);
                for(int i=0;i<n;i++){
                    if(!res[i]) res[i] = indx3;
                }
                return res;
            }
        }
	}
    return res;
}

Compilation message (stderr)

split.cpp: In function 'void dfs_finala(int)':
split.cpp:84:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |         if(!viz[it] && O_o.size() < A) dfs_finala(it);
      |                        ~~~~~~~~~~~^~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:146:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  146 |             if(O_o.size() >= A){
      |                ~~~~~~~~~~~^~~~

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