oj.uz

Submission #341602

# Submission time Handle Problem Language Result Execution time Memory
341602 2020-12-30T07:43:26 Z amunduzbaev Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 169 ms 20444 KB 
/** made by amunduzbaev **/
 
#include <bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define int long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
 
const int N = 2e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
int s, n, m, k;
pii ans;

vii edges[N];
stack<int> ss;
bool used[N], cyc[N];
pii mxd[N];
vii cc;

void dfs(int u, int p){
	if(!cc.empty()) return;
	if(used[u]){
		while(!ss.empty() && ss.top() != u){
			cc.pb(ss.top());
			ss.pop();
		}
		cc.pb(u);return;
	}
	used[u] = 1;
	ss.push(u);
	for(auto x:edges[u]) if(x != p) dfs(x, u);
	if(!ss.empty()) ss.pop();
}

pii merge(pii a, pii b){
	if(a.ff > b.ff) return a;
	if(b.ff > a.ff) return b;
	return mp(a.ff, a.ss + b.ss);
}

pii find_tree(int u, int p){
	vpii tmp;
	for(auto x:edges[u]){
		if(cyc[x] || x == p) continue;
		pii tt = find_tree(x, u);
		tmp.pb(tt);
		mxd[u] = merge(tt, mxd[u]);
	}
	sort(all(tmp));
	int n = sz(tmp);
	if(n >= 2){
		pii b = tmp[n-2], a = tmp[n-1], c = {a.ff + b.ff, 0};
		for(int i=0;i<n;i++){
			if(tmp[i].ff == b.ff) c.ss += tmp[i].ss;
		}
		if(a.ff != b.ff){
			c.ss *= a.ss;
			ans = merge(ans, c);
		}else{
			c.ss *= c.ss;
			for(auto x:tmp){
				if(x.ff == b.ff) c.ss -= x.ss * x.ss;
			}
			c.ss /= 2;
			ans = merge(c, ans);
		}
	}else ans = merge(ans, mxd[u]);
	return { mxd[u].ff+1, mxd[u].ss}; 
}

void solve(){
	cin>>n;
	
	for(int i=0;i<n;i++){
		int a, b;
		cin>>a>>b;
		edges[a].pb(b);
		edges[b].pb(a);
	}
	
	for(int i=1;i<=n;i++) mxd[i] = {0, 1};
	
	dfs(1, -1);
	int cyclen = sz(cc);
	for(auto x:cc) cyc[x] = 1;
	
	for(int i=1;i<=n;i++) if(cyc[i]) find_tree(i, -1);
	
	int p=0;
	map<int, int> mm;
	
	
	for(int i=0;i<cyclen-1;i++){
		while(p < cyclen && p+p <= cyclen+i+i){
			mm[(mxd[cc[p]].ff+p)] += mxd[cc[p]].ss;
			p++;
		}
		mm[mxd[cc[i]].ff+i] -= mxd[cc[i]].ss;
		if(!mm[mxd[cc[i]].ff+i]) mm.erase(mxd[cc[i]].ff+i);
		
		pii tmp = *mm.rbegin();
		
		ans = merge(ans, {mxd[cc[i]].ff+tmp.ff-i, tmp.ss*mxd[cc[i]].ss});
	}
	
	mm.clear();
	p = cyclen-1;
	
	for(int i=cyclen-1;i>=0;i--){
		while(p+p >= cyclen+i+i){
			mm[mxd[cc[p]].ff+cyclen-p] += mxd[cc[p]].ss;
			p--;
		}
		if(mm.size()){
			pii tmp = *mm.rbegin();
			ans = merge(ans, {mxd[cc[i]].ff+i+tmp.ff, tmp.ss*mxd[cc[i]].ss});
		}
	}
	
	cout<<ans.ss<<"\n";
	return;
}

main(){
	fastios
	int t = 0;
	if(!t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

Compilation message

shymbulak.cpp:146:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  146 | main(){
      |      ^

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 5 ms 5356 KB Output is correct
6 Correct 5 ms 5484 KB Output is correct
7 Correct 6 ms 5356 KB Output is correct
8 Correct 6 ms 5356 KB Output is correct
9 Correct 5 ms 5356 KB Output is correct
10 Correct 5 ms 5356 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 10732 KB Output is correct
2 Correct 70 ms 10732 KB Output is correct
3 Correct 54 ms 14308 KB Output is correct
4 Correct 44 ms 10476 KB Output is correct
5 Correct 45 ms 10604 KB Output is correct
6 Correct 169 ms 15852 KB Output is correct
7 Correct 121 ms 13036 KB Output is correct
8 Correct 85 ms 15980 KB Output is correct
9 Correct 86 ms 16192 KB Output is correct
10 Correct 81 ms 16876 KB Output is correct
11 Correct 116 ms 19932 KB Output is correct
12 Correct 124 ms 20444 KB Output is correct