Submission #1060678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060678		aaaaaarroz	Split the Attractions (IOI19_split)	C++17	64 / 100	98 ms	38216 KiB

split

    #include <bits/stdc++.h>
     
    #include "split.h"
     
    #define F first
    #define S second
    #define all(x) x.begin(), x.end()
    #define pb push_back
    #define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
     
    using namespace std;
     
    typedef long long ll;
    typedef pair <ll, ll> pii;
     
    const int N = 1e5 + 7;
    int n, tim, f = -1;
    int bio[N], st[N], ba[N], siz[N];
    vector <int> no;
    vector <int> adj[N], gadj[N];
    vector <pii> fo, u;
     
    void dfs(int x, int p = -1) {
    	bio[x] = 1;
    	st[x] = tim++;
    	ba[x] = st[x];
    	siz[x] = 1;
    	int mx = 0, sum = 0;
    	for (auto y : adj[x]) {
    		if (y == p) continue;
    		if (bio[y]) {
    			if (st[y] < st[x]) ba[x] = min(ba[x], st[y]);
    			continue;
    		}
    		dfs(y, x);
    		ba[x] = min(ba[x], ba[y]);
    		siz[x] += siz[y];
    		mx = max(mx, siz[y]);
    		gadj[x].pb(y);
    		gadj[y].pb(x);
    	}
    	mx = max(mx, n-siz[x]);
    	if (mx <= n/2 && f == -1) {
    		f = x;
    		for (auto y : adj[x]) if (st[y] > st[x] && ba[y] >= st[x]) fo.pb({siz[y], y});
    		if (p != -1) {
    			u.pb({n-siz[x], p});
    			for (auto y : adj[x]) if (st[y] > st[x] && ba[y] < st[x]) u.pb({siz[y], y});
    		}
    	}
    }
     
    void ldfs(int x) {
    	no.pb(x);
    	bio[x] = 1;
    	for (auto y : gadj[x]) if (!bio[y]) ldfs(y);
    }
     
    vector <int> find_split(int nn, int a, int b, int c, vector <int> p, vector <int> q) {
    	n = nn;
    	int m = p.size();
    	int ca = 1, cb = 2, cc = 3;
    	if (a > b) {swap(a, b); swap(ca, cb);};
    	if (a > c) {swap(a, c); swap(ca, cc);};
    	if (b > c) {swap(c, b); swap(cc, cb);};
    	
    	for (int i = 0; i < m; i++) {
    		adj[p[i]].pb(q[i]);
    		adj[q[i]].pb(p[i]);
    	}
    	dfs(0);
    	memset(bio, 0, sizeof bio);
    	
    	int x = f, sum = 0;
    	sort(all(fo)); sort(all(u)); reverse(all(u));
    	for (auto it : u) sum += it.F;
    	vector <int> res(n, 0);
    	
    	
    	if (!(!fo.empty() && fo.back().F >= a) && sum < a) return res;
    	bio[x] = 1;
    	
    	for (int i = 0; i < n; i++) res[i] = cc;
    	
    	if (sum < a) ldfs(fo.back().S);
    	else {
    		sum = 0;
    		for (int i = 0; i < u.size(); i++) {
    			sum += u[i].F;
    			if (sum < a) ldfs(u[i].S);
    			else {
    				vector <int> tmp; tmp = no; no.clear();
    				ldfs(u[i].S);
    				for (auto y : no) bio[y] = 0;
    				int fx = u[i].S;
    				for (auto y : no) {
    					for (auto z : adj[y]) {
    						if (bio[z] && z != x) fx = y;
    					}
    					if (fx != -1) break;
    				}
    				no.clear();
    				no = tmp;
    				ldfs(fx);
    				break;
    			}
    		}
    	}
    	
    	for (int i = 0; i < a; i++) res[no[i]] = ca;
    	no.clear();
    	ldfs(x);
    	if (no.size() < b) exit(0);
    	for (int i = 0; i < b; i++) res[no[i]] = cb;
    	return res;
    }

Compilation message (stderr)

split.cpp: In function 'void dfs(int, int)':
split.cpp:28:18: warning: unused variable 'sum' [-Wunused-variable]
   28 |      int mx = 0, sum = 0;
      |                  ^~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:88:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |       for (int i = 0; i < u.size(); i++) {
      |                       ~~^~~~~~~~~~
split.cpp:113:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |      if (no.size() < b) exit(0);
      |          ~~~~~~~~~~^~~

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