oj.uz

Submission #392637

# Submission time Handle Problem Language Result Execution time Memory
392637 2021-04-21T11:52:35 Z vanic Shymbulak (IZhO14_shymbulak) C++14
70 / 100
 269 ms 16468 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 5032 KB Output is correct
3 Correct 4 ms 5024 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Incorrect 4 ms 5068 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5284 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 6 ms 5160 KB Output is correct
4 Correct 4 ms 5156 KB Output is correct
5 Correct 6 ms 5324 KB Output is correct
6 Correct 5 ms 5324 KB Output is correct
7 Correct 6 ms 5324 KB Output is correct
8 Correct 6 ms 5324 KB Output is correct
9 Correct 6 ms 5324 KB Output is correct
10 Correct 6 ms 5292 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 9848 KB Output is correct
2 Correct 78 ms 10088 KB Output is correct
3 Correct 269 ms 14548 KB Output is correct
4 Correct 49 ms 9568 KB Output is correct
5 Correct 49 ms 9472 KB Output is correct
6 Correct 208 ms 14084 KB Output is correct
7 Correct 134 ms 13040 KB Output is correct
8 Correct 98 ms 13508 KB Output is correct
9 Correct 123 ms 13572 KB Output is correct
10 Correct 104 ms 14404 KB Output is correct
11 Correct 102 ms 16056 KB Output is correct
12 Correct 107 ms 16468 KB Output is correct