Submission #1197249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197249		CELD_07	Parachute rings (IOI12_rings)	C++20	37 / 100	956 ms	173628 KiB

rings

#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 998244353
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
#define dgb(x) cout<<#x<<" : "<<x<<"\n"
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;
}
inline ll q(vector<ll>& v1, ll l, ll r){
return (l==0 ? v1[r]: v1[r]-v1[l-1]);
}
vector<vector<ll>> adj;
vector<ll> dg, r1;
vector<vector<ll>> p, s;
vector<pair<ll, ll>> v1, v2;
inline ll _find(ll c, ll a){
if(p[c][a]!=a)p[c][a]=_find(c, p[c][a]);
return p[c][a];
}
ll cnt3=0, cnt4=0;
inline void _union(ll a, ll b, ll c){
//if(c==0)cout<<a<<" "<<b<<" "<<v2[c].ft<<" "<<_find(c, b)<<endl;
a=_find(c, a);
b=_find(c, b);
if(a==b){v2[c].ft++;v2[c].sd=s[c][a];return;}
if(s[c][a]<s[c][b])swap(a, b);
s[c][a]+=s[c][b];
p[c][b]=a;
}
void Init(int N){
cnt3=0;
cnt4=0;
vector<pair<ll, ll>>().swap(v1);
vector<pair<ll, ll>>().swap(v2);
vector<vector<ll>>().swap(adj);
vector<vector<ll>>().swap(s);
vector<vector<ll>>().swap(p);
vector<ll>().swap(r1);
vector<ll>().swap(dg);
adj.resize(N+1);
p.resize(6, vector<ll>(N+1));
s.assign(6, vector<ll>(N+1, 1));
v2.assign(6, {0, 0});
for(int i=0; i<6; i++)for(int j=0; j<=N; j++)p[i][j]=j;
r1.assign(5, -1);
dg.assign(N+1, 0);
}
void Link(int A, int B){
A++;
B++;
v1.push_back({A, B});
adj[A].push_back(B);
adj[B].push_back(A);
dg[A]++;
dg[B]++;
_union(A, B, 5);
//cout<<v2[5].ft<<" "<<v2[5].sd<<endl;
ll o=r1[0], o1=r1[4];
if(dg[A]==3){if(r1[0]==-1)r1[0]=A;cnt3++;}
if(dg[B]==3){if(r1[0]==-1)r1[0]=B;cnt3++;}
if(dg[A]==4){if(r1[4]==-1)r1[4]=A;cnt4++;}
if(dg[B]==4){if(r1[4]==-1)r1[4]=B;cnt4++;}
if(o!=r1[0]){
for(int i=0; i<adj[r1[0]].size(); i++)r1[i+1]=adj[r1[0]][i];
for(auto& [x, y]: v1){
//cout<<-1<<" "<<x<<" "<<y<<endl;
for(int i=0; i<4; i++)if(x!=r1[i] && y!=r1[i])_union(x, y, i);
}
}else if(o!=-1){
for(int i=0; i<4; i++)if(A!=r1[i] && B!=r1[i])_union(B, A, i);
}
if(o1!=r1[4]){
for(auto& [x, y]: v1){
if(x!=r1[4] && y!=r1[4])_union(x, y, 4);
}
}else if(o1!=-1)if(A!=r1[4] && B!=r1[4])_union(A, B, 4);
}
int CountCritical(){
if(cnt4!=0){
if(cnt4==1 && v2[4].ft==0)return 1;
return 0;
}
if(cnt3!=0){
ll cnt=0;
for(int i=0; i<4; i++){//cout<<i<<" "<<r1[i]<<" "<<v2[i].ft<<" "<<v2[i].sd<<endl;
ll cnt1=0;
if(dg[r1[i]]==3)cnt1++;
for(auto y: adj[r1[i]]){ll o1=adj[y].size();if(o1==3)cnt1++;}
//cout<<r1[i]-1<<" "<<cnt1<<" "<<cnt3<<endl;
if(cnt1==cnt3 && v2[i].ft==0)cnt++;
}
return cnt;
}
//cout<<v2[5].ft<<" "<<v2[5].sd<<endl;
if(v2[5].ft==0){ll k=adj.size();return k-1;}
if(v2[5].ft==1)return v2[5].sd;
return 0;
}
/*
int main(){
    //freopen("time.in", "r", stdin);freopen("time.out", "w", stdout);
    //ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    //PRESICION(15)
    //int t;cin>>t;while(t--)
    Init(7);
    while(1){
    ll a, b;
    cin>>a;
    if(a==-1)cout<<CountCritical()<<endl;
    else {cin>>b;Link(a, b);}
    }
}

*/

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31