제출 #17589

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17589		comet	관광지 (IZhO14_shymbulak)	C++98	100 / 100	115 ms	22144 KiB

shymbulak

#include<iostream>
#include<vector>
#include<deque>
#include<cstdio>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
vector<int> path[222222];
vector<int> cycle;
int n,chk[222222],T,N;
ll Max,cnt,a[222222],b[222222],CNT[422222];
bool isCycle[222222];
deque<ll> index,value;
pp dfs(int v,int p){
	int u,i,z0=0,cnt0=1;
	pp t;
	for(i=0;i<path[v].size();i++){
		u=path[v][i];
		if(u==p||isCycle[u])continue;
		t=dfs(u,v);

		if(z0+t.first+1>Max)Max=z0+t.first+1,cnt=(1ll*cnt0)*t.second;
		else if(z0+t.first+1==Max)cnt+=(1ll*cnt0)*t.second;

		if(z0<t.first)z0=t.first,cnt0=t.second;
		else if(z0==t.first)cnt0+=t.second;
	}
	return pp(z0+1,cnt0);
}
int find_cycle(int v,int p){
	chk[v]=++T;
	int u,i,ret=1e9;
	for(i=0;i<path[v].size();i++){
		u=path[v][i];
		if(u==p)continue;
		if(chk[u]){
			isCycle[v]=1;
			cycle.push_back(v);
			return chk[u];
		}
		ret=min(ret,find_cycle(u,v));
		if(ret<=chk[v]){
			isCycle[v]=1;
			cycle.push_back(v);
			return ret;
		}
	}
	return ret;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	int x,y;
	for(int i=0;i<n;i++){
		cin>>x>>y;
		path[x].push_back(y);
		path[y].push_back(x);
	}
	find_cycle(1,0);
	pp tt;
	for(int i=0;i<cycle.size();i++){
		tt=dfs(cycle[i],0);
		a[i]=tt.first;
		b[i]=tt.second;
	}
	N=cycle.size()+cycle.size()/2;
	for(int i=cycle.size();i<N;i++)a[i]=a[i-cycle.size()],b[i]=b[i-cycle.size()];
	ll z0,z1,cnt0,cnt1,len=cycle.size()/2,t=0;
	index.push_back(0);
	value.push_back(a[0]);
	CNT[a[0]+N]+=b[0];
	for(int i=1;i<N;i++){
		while((!index.empty())&&index.front()+len<i){
			CNT[value.front()+N]-=b[index.front()];
			index.pop_front();
			value.pop_front();
		}
		if(i>=len){
			z0=value.empty()?0:value.front();
			cnt0=value.empty()?0:CNT[value.front()+N];
			z1=a[i];
			cnt1=b[i];
			if(z0+z1+t>Max)Max=z0+z1+t,cnt=cnt0*cnt1;
			else if(z0+z1+t==Max)cnt+=cnt0*cnt1;
		}
		t++;
		index.push_back(i);
		value.push_back(a[i]-t);
		CNT[a[i]-t+N]+=b[i];
		while(value.size()>1&&value[value.size()-2]<value.back()){
			CNT[value[value.size()-2]+N]-=b[index[index.size()-2]];
			value[value.size()-2]=value.back();
			index[index.size()-2]=index.back();
			value.pop_back();
			index.pop_back();
		}
	}
	cout<<cnt;
}

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