oj.uz

Submission #337754

# Submission time Handle Problem Language Result Execution time Memory
337754 2020-12-21T13:45:39 Z Kerim Shymbulak (IZhO14_shymbulak) C++17
0 / 100
 144 ms 21932 KB 
#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,ll> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
vector<PII>g[MAXN];
stack<int>st;
vector<int>adj[MAXN],v;
int vis[MAXN];
void dfs1(int nd,int pr){
	if(!v.empty())
		return;
	if(vis[nd]){
		while(!st.empty() and st.top()!=nd)
			v.pb(st.top()),st.pop();
		v.pb(nd);
		return;
	}
	st.push(nd);
	vis[nd]=1;
	tr(it,g[nd])
		if(it->ss!=pr)
			dfs1(it->ff,it->ss);
	st.pop();
}
PII dp[MAXN],ans;
PII merge(PII x,PII y){
	if(x.ff>y.ff)
		return x;
	if(y.ff>x.ff)
		return y;
	return mp(x.ff,x.ss+y.ss);
}
void dfs(int nd,int pr){
	dp[nd]=mp(0,1);
	vector<PII>v;
	tr(it,adj[nd])
		if(*it!=pr and !vis[*it]){
			dfs(*it,nd);
			v.pb(dp[*it]);
			dp[nd]=merge(dp[nd],dp[*it]);
		}
	sort(all(v));
	if(int(v.size())>=2){
		PII a=v[v.size()-2],b=v[v.size()-1];
		ans=merge(ans,mp(a.ff+b.ff,a.ss*b.ss));
	}
	else
		ans=merge(ans,dp[nd]);
	dp[nd].ff++;
}
int main(){
    //freopen("file.in", "r", stdin);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].pb(mp(v,i));adj[u].pb(v);
		g[v].pb(mp(u,i));adj[v].pb(u);
	}
	dfs1(1,-1);int sz=int(v.size());
	memset(vis,0,sizeof vis);
	tr(it,v)
		vis[*it]=1;
	vector<PII>g;
	tr(it,v)
		dfs(*it,-1),g.pb(mp(dp[*it].ff-1,dp[*it].ss));
	//cout<<ans.ff<<" "<<ans.ss<<endl;
	for(int i=0;i<sz;i++)
		for(int j=i+1;j<sz;j++)
			ans=merge(ans,mp(g[i].ff+g[j].ff+min(j-i,sz-j+i),g[i].ss*g[j].ss*(1+(j-i==sz-j+i))));
	//cout<<ans.ff<<" "<<ans.ss<<endl;
	printf("%lld\n",ans.ss);
	return 0;
}

Compilation message

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
shymbulak.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10476 KB Output is correct
2 Incorrect 8 ms 10476 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10604 KB Output is correct
2 Incorrect 8 ms 10604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 21644 KB Output is correct
2 Incorrect 144 ms 21932 KB Output isn't correct
3 Halted 0 ms 0 KB -