Submission #392637

#	Time	Username	Problem	Language	Result	Execution time	Memory
392637		vanic	Shymbulak (IZhO14_shymbulak)	C++14	70 / 100	269 ms	16468 KiB

shymbulak

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <set>
#include <stack>
#include <map>
#include <vector>
#include <queue>
#include <cstring>
#include <array>
#include <bitset>

using namespace std;

typedef long long ll;

const int maxn=2e5+5, Log=18, pot=(1<<Log);

struct tournament{
	int t[pot*2];
	int k[pot*2];
	int prop[pot*2];
	void propagate(int x){
		if(!prop[x]){
			return;
		}
		t[x]+=prop[x];
		if(x<pot){
			prop[x*2]+=prop[x];
			prop[x*2+1]+=prop[x];
		}
		prop[x]=0;
	}
	void cisti(int L, int D, int x, int val){
		propagate(x);
		if(L==val && D==val){
			return;
		}
		if((L+D)/2>=val){
			cisti(L, (L+D)/2, x*2, val);
		}
		else{
			cisti((L+D)/2+1, D, x*2+1, val);
		}
	}
	void update1(int x, int val, int komb){
		cisti(0, pot-1, 1, x-pot);
		t[x]=val;
		k[x]=komb;
		for(x/=2; x>0; x/=2){
			propagate(x*2);
			propagate(x*2+1);
			if(t[x*2]>t[x*2+1]){
				t[x]=t[x*2];
				k[x]=k[x*2];
			}
			else if(t[x*2]<t[x*2+1]){
				t[x]=t[x*2+1];
				k[x]=k[x*2+1];
			}
			else{
				t[x]=t[x*2];
				k[x]=k[x*2]+k[x*2+1];
			}
		}
	}
	void update(int x, int val){
		t[x]+=val;
		for(x/=2; x>0; x/=2){
			propagate(x*2);
			propagate(x*2+1);
			if(t[x*2]>t[x*2+1]){
				t[x]=t[x*2];
				k[x]=k[x*2];
			}
			else if(t[x*2]<t[x*2+1]){
				t[x]=t[x*2+1];
				k[x]=k[x*2+1];
			}
			else{
				t[x]=t[x*2];
				k[x]=k[x*2]+k[x*2+1];
			}
		}
	}
	void update2(int L, int D, int x, int l, int d, int val){
		propagate(x);
		if(L>=l && D<=d){
			update(x, val);
			if(x<pot){
				prop[x*2]+=val;
				prop[x*2+1]+=val;
			}
			return;
		}
		if((L+D)/2>=l){
			update2(L, (L+D)/2, x*2, l, d, val);
		}
		if((L+D)/2+1<=d){
			update2((L+D)/2+1, D, x*2+1, l, d, val);
		}
	}
};


vector < int > ms[maxn];
bitset < maxn > bio;
vector < int > sad;
vector < int > da;
bitset < maxn > cik;
tournament T;


bool ciklus(int x, int prosl){
	if(bio[x]){
		bool p=0;
		for(int i=0; i<(int)sad.size(); i++){
			if(sad[i]==x){
				p=1;
			}
			if(p){
				da.push_back(sad[i]);
				cik[sad[i]]=1;
			}
		}
		return 1;
	}
	sad.push_back(x);
	bio[x]=1;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl){
			if(ciklus(ms[x][i], x)){
				return 1;
			}
		}
	}
	bio[x]=0;
	sad.pop_back();
	return 0;
}

vector < int > dulj;

void siri(int x, int dep){
//	cout << "proso " << x << endl;
	bio[x]=1;
	dulj.push_back(dep);
	for(int i=0; i<(int)ms[x].size(); i++){
		if(!cik[ms[x][i]] && !bio[ms[x][i]]){
			siri(ms[x][i], dep+1);
		}
	}
}

vector < array < int, 4 > > svi;

ll komba;
int curr;

int bfs(int x, int prosl){
	queue < pair < int, int > > q;
	q.push({x, prosl});
	pair < int, int > p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		prosl=p.second;
		x=p.first;
		for(int i=0; i<(int)ms[x].size(); i++){
			if(ms[x][i]!=prosl && !cik[ms[x][i]]){
//				cout << "pusham " << ms[x][i] << endl;
				q.push({ms[x][i], x});
			}
		}
	}
	return x;
}

vector < int > put;

bool dfs(int x, int prosl, int y){
	put.push_back(x);
	if(x==y){
		return 1;
	}
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl && !cik[ms[x][i]]){
			if(dfs(ms[x][i], x, y)){
				return 1;
			}
		}
	}
	put.pop_back();
	return 0;
}

int nadji(int x, int prosl, int d){
	if(!d){
		return 1;
	}
	d--;
	int br=0;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(ms[x][i]!=prosl && !cik[ms[x][i]]){
			br+=nadji(ms[x][i], x, d);
		}
	}
	return br;
}

void rijesi(int x){
	int poc=x;
	cik[poc]=0;
	x=bfs(x, x);
	int y=bfs(x, x);
	dfs(x, x, y);
	int dulj=put.size();
/*	for(int i=0; i<dulj; i++){
		cout << put[i] << ' ';
	}
	cout << endl;*/
	curr=dulj-1;
	int br1, br2;
	if(dulj&1){
		br1=nadji(put[dulj/2], put[dulj/2], dulj/2);
		komba=(ll)br1*(br1-1)/2;
	}
	else{
		br1=nadji(put[dulj/2-1], put[dulj/2], dulj/2-1);
		br2=nadji(put[dulj/2], put[dulj/2-1], dulj/2-1);
		komba=(ll)br1*br2;
	}
	cik[poc]=1;
	put.clear();
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	int a, b;
	for(int i=0; i<n; i++){
		cin >> a >> b;
		a--;
		b--;
		ms[a].push_back(b);
		ms[b].push_back(a);
	}
	ciklus(0, 0);
	bio.reset();
/*	for(int i=0; i<n; i++){
		if(cik[i]){
			cout << i << ' ';
		}
	}
	cout << endl;*/
	int br1;
	int val1;
	int pos;
	int m=da.size();
	for(int i=0; i<m; i++){
//		cout << da[i] << ' ';
		siri(da[i], 0);
		sort(dulj.begin(), dulj.end());
		br1=0;
		pos=dulj.size()-1;
		val1=dulj.back();
		while(pos>-1 && val1==dulj[pos]){
			br1++;
			pos--;
		}
		svi.push_back({val1, br1});
		dulj.clear();
	}
//	cout << endl;
/*	for(int i=0; i<m; i++){
		cout << svi[i][0] << ' ' << svi[i][1] << endl;
	}*/
	int l1, d1, l2, d2;
	for(int i=0; i<m; i++){
		T.update1(i+pot, svi[i][0], svi[i][1]);
	}
	int maksi=0;
	ll komb=0;
	int val;
	for(int i=0; i<m; i++){
		T.update1(i+pot, -maxn, 0);
		if(!i){
			if(!(m&1) && i<m/2){
				T.update1(i+pot+m/2, svi[i+m/2][0], svi[i+m/2][1]*2);
			}
			for(int j=1; j<m; j++){
				T.update2(0, pot-1, 1, j, j, min(j, m-j));
			}
		}
		else{
			if(!(m&1) && i<m/2){
				T.update1(i+pot+m/2, svi[i+m/2][0]+m/2-1, svi[i+m/2][1]*2);
			}
			l1=i-m/2;
			d1=i-1;
			if(l1<0){
				l2=l1+m;
				d2=m-1;
				l1=0;
				T.update2(0, pot-1, 1, l2, d2, 1);
			}
			T.update2(0, pot-1, 1, l1, d1, 1);
			l1=i;
			d1=i+m/2-1;
			if(d1>=m){
				l2=0;
				d2=d1-m;
				d1=m-1;
				T.update2(0, pot-1, 1, l2, d2, -1);
			}
			T.update2(0, pot-1, 1, l1, d1, -1);
		}
		val=T.t[1]+svi[i][0];
//		cout << val << ' ' << svi[i][1] << ' ' << T.k[1] << endl;
		if(val>maksi){
			maksi=val;
			komb=T.k[1]*svi[i][1];
		}
		else if(val==maksi){
			komb+=T.k[1]*svi[i][1];
		}
		if(!(m&1) && i<m/2){
			T.update1(i+pot+m/2, svi[i+m/2][0]+m/2, svi[i+m/2][1]);
		}
	}
	bio.reset();
	for(int i=0; i<m; i++){
		rijesi(da[i]);
		if(curr>maksi){
			maksi=curr;
			komb=komba;
		}
		else if(curr==maksi){
			komb+=komba;
		}
	}
	cout << komb << '\n';
//	cout << maksi << endl;
	return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50