Submission #1215277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215277		CELD_07	Split the Attractions (IOI19_split)	C++20	22 / 100	49 ms	11076 KiB

split

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
vector<vector<ll>> adj;
vector<ll> v1;
ll l, l1, l2;
pair<ll, ll> p1={-1, -1};
inline void dfs(ll n, ll p, ll o1, ll o2, ll o3){
v1[n]=1;
for(auto y: adj[n]){
if(y==p)continue;
dfs(y, n, o1, o2, o3);
v1[n]+=v1[y];
}
if(v1[n]>=o1 && o3-v1[n]>=o2)p1={n, p};
}
ll cnt=0;
inline void dfs1(vector<int>& res, ll n, ll p, ll o2, ll k){
//cout<<n<<" "<<p<<" "<<cnt<<" "<<o2<<" "<<k<<endl;
if(cnt==o2)return;
res[n]=k;
cnt++;
for(auto y: adj[n]){
if(y!=p)dfs1(res, y, n, o2, k);
}
}
std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q){
vector<vector<ll>>().swap(adj);
vector<ll>().swap(v1);
v1.resize(n+1, -1);
adj.resize(n+1);
l=a;
l1=b;
l2=c;
p1={-1, -1};
for(int i=0; i<p.size(); i++){
adj[p[i]].push_back(q[i]);
adj[q[i]].push_back(p[i]);
}
vector<int>res, v2={a, b, c};
ll o7=p.size();
if(o7==n-1){
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
if(i==j)continue;
cnt=0;
p1={-1, -1};
ll o2;
if(min(i, j)!=0)o2=1;
else if(max(i, j)!=2)o2=3;
else o2=2;
vector<int>().swap(res);
res.assign(n, o2);
dfs(0, 0, v2[i], v2[j], n);
if(p1.ft==-1)continue;
//cout<<p1.ft<<" "<<p1.sd<<" "<<i<<" "<<j<<endl;
cnt=0;
dfs1(res, p1.ft, p1.sd, v2[i], i+1);
cnt=0;
dfs1(res, p1.sd, p1.ft, v2[j], j+1);
return res;
}
}
}
vector<int>().swap(res);
res.assign(n, 0);
return res;
}/*
int main(){
vector<int> res=find_split(8, 2, 3, 3, {0, 1, 2, 2, 2, 2, 0}, {1, 2, 3, 4, 5, 6, 7});
for(auto y: res)cout<<y<<" ";
cout<<endl;
}
*/

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