Submission #270114

#	Time	Username	Problem	Language	Result	Execution time	Memory
270114		shayan_p	Parachute rings (IOI12_rings)	C++14	100 / 100	1850 ms	111832 KiB

rings

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

struct dsu{
    int par[maxn];
    void init(int n){
	fill(par, par + n, -1);
    }
    int fnd(int u){
	return par[u] < 0 ? u : par[u] = fnd(par[u]);
    }
    bool mrg(int a, int b){
	if( (a = fnd(a)) == (b = fnd(b)) )
	    return 0;
	if(par[a] > par[b])
	    swap(a, b);
	par[a]+= par[b];
	par[b] = a;
	return 1;
    }
};
struct solver{
    bool ok;
    int d[maxn];
    dsu ds;
    void init(int n){
	ok = 1;
	ds.init(n);
	fill(d, d + n, 0);
    }
    void add(int a, int b){
	if((++d[a]) > 2 || (++d[b]) > 2)
	    ok = 0;
	if(!ds.mrg(a, b))
	    ok = 0;
    }
};
solver sol[4];
dsu ds;

vector<pii> ed;
vector<int> imps;
vector<int> v[maxn];
int n;
int CYC;
bool bad;

void Init(int n){
    ::n = n;
    for(int i = 0; i < n; i++)
	v[i].clear();
    imps.clear();
    ed.clear();
    for(int i = 0; i < 4; i++)
	sol[i].init(n);
    ds.init(n);
    CYC = -1;
    bad = 0;
}
void Link(int a, int b){
    ed.PB({a, b});
    v[a].PB(b), v[b].PB(a);
    if(sz(v[a]) < sz(v[b]))
	swap(a, b);
    if(imps.empty() == 0){
	for(int i = 0; i < 4; i++){
	    if(a != imps[i] && b != imps[i])
		sol[i].add(a, b);
	}
    }
    if(imps.empty() && sz(v[a]) > 2){
	assert(sz(v[a]) == 3);
	imps = v[a];
	imps.PB(a);
	for(pii p : ed){
	    for(int i = 0; i < 4; i++){
		if(p.F != imps[i] && p.S != imps[i])
		    sol[i].add(p.F, p.S);
	    }
	}
    }
    if(!ds.mrg(a, b)){
	if(CYC != -1)
	    bad = 1;
	CYC = -ds.par[ ds.fnd(a) ];
    }
}
int CountCritical(){
    int ans = 0;
    if(imps.empty()){
	if(bad == 0)
	    ans = CYC == -1 ? n : CYC;
    }
    else{
	for(int i = 0; i < 4; i++)
	    ans+= sol[i].ok;
    }
    return ans;
}

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