oj.uz

Submission #147304

# Submission time Handle Problem Language Result Execution time Memory
147304 2019-08-28T19:05:52 Z liwi Split the Attractions (IOI19_split) C++14
11 / 100
 109 ms 13400 KB 
#include "split.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define MOD2 1190492669
#define SEED 131
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);

#define MAXN 100005

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

mt19937 g1(time(0));

int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}

ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

int num_nodes,sz[MAXN],A,B,C;
bool vis[MAXN],RR[10];
vector<int> connections[MAXN],res;

inline void reset(){
	memset(vis,false,sizeof vis);
	memset(sz,0,sizeof sz);
	memset(RR,0,sizeof RR);
	for(int i=0; i<num_nodes; i++)
		connections[i].clear();
	for(int i=0; i<res.size(); i++)
		res[i] = 0;
}

inline void bad(){
	for(int i=0; i<num_nodes; i++)
		res[i] = 0;
}

vector<int> subtaskTwo(int wanted_sz){
	queue<int> q;
	q.push(0);
	vis[0] = true;
	wanted_sz--;
	while(q.size()){
		int node = q.front(); q.pop();
		for(int check:connections[node]){
			if(vis[check] || !wanted_sz) continue;
			vis[check] = true;
			wanted_sz--;
			q.push(check);
		}
	}
	vector<int> v;
	for(int i=0; i<num_nodes; i++)
		if(vis[i])
			v.pb(i);
	return v;
}

int gsz(int node, int prev){
	sz[node] = 1;
	for(int check:connections[node]){
		if(check == prev) continue;
		sz[node]+=gsz(check,node);
	}
	return sz[node];
}

void mark(int node, int prev, int &cnt, int ss){
	if(cnt == 0) return;
	res[node] = ss, cnt--;
	for(int check:connections[node]){
		if(check == prev) continue;
		mark(check,node,cnt,ss);
	}
}

void markrem(int node, int blocked, int &cnt, int ss){
	queue<int> q;
	q.push(node);
	vis[node] = true;
	while(q.size()){
		int node = q.front(); q.pop();
		res[node] = ss;
		for(int check:connections[node]){
			if(vis[check] || check == blocked || !cnt) continue;
			vis[check] = true, cnt--;
			q.push(check);
		}
	}
}

bool solve(int node, int prev){
	vector<pii> t = {{A,1},{B,2},{C,3}}; sort(all(t));
	if(sz[node] >= t[0].first && num_nodes-sz[node] >= t[1].first){
		mark(node,prev,t[0].first,t[0].second);
		markrem(prev,node,t[1].first,t[1].second);
		RR[t[0].second] = RR[t[1].second] = true;
		return true;
	}
	for(int check:connections[node]){
		if(check == prev) continue;
		if(solve(check,node)) return true;
	}
	return false;
}

vector<int> find_split(int n, int a, int b, int c, vector<int>p, vector<int>q){
	num_nodes = n, A = a, B = b, C = c, res.resize(n);
	reset();
	for(int i=0; i<p.size(); i++){
		int f = p[i], s = q[i];
		connections[f].pb(s);
		connections[s].pb(f);
	}
	if(a == 1){
		vector<int> v = subtaskTwo(min(b,c));
		for(int check:v)
			res[check] = (b<c?2:3);
		bool done_one = false;
		for(int i=0; i<num_nodes; i++){
			if(vis[i]) continue;
			if(!done_one) res[i] = 1, done_one = true;
			else res[i] = (b<c?3:2);
		}
		return res;
	}else if(p.size() == n-1){
		gsz(1,-1);
		if(!solve(1,-1)){
			bad();
			return res;
		}
		for(int i=0; i<num_nodes; i++)
			if(res[i] == 0)
				res[i] = (RR[1]?RR[2]?3:2:1);
		return res;
	}
	bad();
	return res;
}

inline void pr(vector<int> a){
	for(int check:a) printf("%d ",check); printf("\n");
}

Compilation message

split.cpp: In function 'void reset()':
split.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<res.size(); i++)
               ~^~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:140:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<p.size(); i++){
               ~^~~~~~~~~
split.cpp:156:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  }else if(p.size() == n-1){
           ~~~~~~~~~^~~~~~
split.cpp: In function 'void pr(std::vector<int>)':
split.cpp:172:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int check:a) printf("%d ",check); printf("\n");
  ^~~
split.cpp:172:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int check:a) printf("%d ",check); printf("\n");
                                        ^~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB ok, correct split
2 Correct 5 ms 3192 KB ok, correct split
3 Correct 5 ms 3196 KB ok, correct split
4 Incorrect 5 ms 3192 KB jury found a solution, contestant did not
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB ok, correct split
2 Correct 5 ms 3192 KB ok, correct split
3 Correct 5 ms 3192 KB ok, correct split
4 Correct 99 ms 11640 KB ok, correct split
5 Correct 81 ms 10228 KB ok, correct split
6 Correct 66 ms 9720 KB ok, correct split
7 Correct 72 ms 10104 KB ok, correct split
8 Correct 109 ms 13400 KB ok, correct split
9 Correct 79 ms 10164 KB ok, correct split
10 Correct 60 ms 10352 KB ok, correct split
11 Correct 65 ms 10444 KB ok, correct split
12 Correct 63 ms 10736 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3192 KB invalid split: #1=3, #2=1, #3=1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3192 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB ok, correct split
2 Correct 5 ms 3192 KB ok, correct split
3 Correct 5 ms 3196 KB ok, correct split
4 Incorrect 5 ms 3192 KB jury found a solution, contestant did not
5 Halted 0 ms 0 KB -