oj.uz

Submission #337808

# Submission time Handle Problem Language Result Execution time Memory
337808 2020-12-21T18:01:18 Z Kerim Shymbulak (IZhO14_shymbulak) C++17
50 / 100
 130 ms 42992 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 b=v[v.size()-2],a=v[v.size()-1];
		PII c=mp(a.ff+b.ff,0LL);
		for(int i=0;i<int(v.size());i++)
			if(v[i].ff==b.ff)
				c.ss+=v[i].ss;
		if(a.ff!=b.ff){
			c.ss*=a.ss;
			ans=merge(ans,c);
		}	
		else{
			c.ss*=c.ss;
			for(int i=0;i<int(v.size());i++)
				if(v[i].ff==b.ff)
					c.ss-=v[i].ss*v[i].ss;
			c.ss/=2;
			ans=merge(ans,c);
		}
	}
	else
		ans=merge(ans,dp[nd]);
	dp[nd].ff++;
}
map<int,ll>a;
int main(){
    //freopen("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);
	}
	if(n>100000){
		printf("%d\n",n);
		return 0;	
	}
	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));
	int p=0;
	for(int i=0;i<sz-1;i++){
		while(p<sz and p+p<=sz+i+i)
			a[g[p].ff+p]+=g[p].ss,p++;
		a[g[i].ff+i]-=g[i].ss;
		if(!a[g[i].ff+i])
			a.erase(g[i].ff+i);
		PII tmp=*a.rbegin();
		ans=merge(ans,mp(tmp.ff+g[i].ff-i,g[i].ss*tmp.ss));
	}p=sz-1;a.clear();
	for(int i=sz-1;i>=0;i--){
		while(p+p>=sz+i+i)
			a[g[p].ff+sz-p]+=g[p].ss,p--;	
		if(a.size()){
			PII tmp=*a.rbegin();
			ans=merge(ans,mp(tmp.ff+g[i].ff+i,g[i].ss*tmp.ss));	
		}
	}
	/*
	for(int i=0;i<sz;i++)
		for(int j=i+1;j<sz;j++){
			if(j-i<=sz-j+i)
				ans=merge(ans,mp(g[i].ff+g[j].ff+j-i,g[i].ss*g[j].ss));
			if(j-i>=sz-j+i)
				ans=merge(ans,mp(g[i].ff+g[j].ff+sz-j+i,g[i].ss*g[j].ss));
		}*/
	printf("%lld\n",ans.ss);
	return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10476 KB Output is correct
2 Correct 7 ms 10476 KB Output is correct
3 Correct 7 ms 10476 KB Output is correct
4 Correct 7 ms 10476 KB Output is correct
5 Correct 7 ms 10476 KB Output is correct
6 Correct 7 ms 10476 KB Output is correct
7 Correct 7 ms 10476 KB Output is correct
8 Correct 7 ms 10476 KB Output is correct
9 Correct 7 ms 10476 KB Output is correct
10 Correct 7 ms 10476 KB Output is correct
11 Correct 7 ms 10476 KB Output is correct
12 Correct 7 ms 10476 KB Output is correct
13 Correct 7 ms 10476 KB Output is correct
14 Correct 7 ms 10604 KB Output is correct
15 Correct 7 ms 10604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10604 KB Output is correct
2 Correct 7 ms 10604 KB Output is correct
3 Correct 8 ms 10604 KB Output is correct
4 Correct 8 ms 10604 KB Output is correct
5 Correct 10 ms 10988 KB Output is correct
6 Correct 10 ms 11244 KB Output is correct
7 Correct 10 ms 10988 KB Output is correct
8 Correct 10 ms 10988 KB Output is correct
9 Correct 10 ms 10988 KB Output is correct
10 Correct 10 ms 10988 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 20640 KB Output is correct
2 Correct 126 ms 20716 KB Output is correct
3 Runtime error 79 ms 42992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -