oj.uz

Submission #116033

# Submission time Handle Problem Language Result Execution time Memory
116033 2019-06-10T08:54:15 Z tmwilliamlin168 Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 148 ms 15864 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pil pair<int, ll>

const int mxN=2e5;
int n, qh, qt;
vector<int> adj[mxN], cyc;
pil ans, a[mxN], qu[mxN];
bool vis[mxN], ic[mxN];

pil operator+(const pil &a, const pil &b) {
	return pil(max(a.first, b.first), (a.first>=b.first?a.second:0)+(a.first<=b.first?b.second:0));
}

bool dfs1(int u=0, int p=-1) {
	if(vis[u]) {
		cyc.push_back(u);
		return 1;
	}
	vis[u]=1;
	for(int v : adj[u]) {
		if(v^p&&dfs1(v, u)) {
			if(u==cyc[0])
				return 0;
			cyc.push_back(u);
			return 1;
		}
	}
	return 0;
}

void dfs2(int u, int p=-1) {
	a[u]=pil(0, 1);
	for(int v : adj[u]) {
		if(v==p||ic[v])
			continue;
		dfs2(v, u);
		ans=ans+pil(++a[v].first+a[u].first, a[v].second*a[u].second);
		a[u]=a[u]+a[v];
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for(int i=0, u, v; i<n; ++i) {
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs1();
	for(int c : cyc)
		ic[c]=1;
	for(int c : cyc)
		dfs2(c);
	for(int i=0, cs=cyc.size(); i<2*cs; ++i) {
		pil u=a[cyc[i%cs]];
		if(i>=cs)
			ans=ans+pil(qu[qh].first+u.first+i, qu[qh].second*u.second);
		while(qt>qh&&qu[qt-1].first<u.first-i)
			--qt;
		if(qt==qh||qu[qt-1].first>u.first-i)
			qu[qt++]=pil(u.first-i, 0);
		qu[qt-1].second+=u.second;
		if(i>=cs/2) {
			pil v=a[cyc[(i-cs/2)%cs]];
			if(qu[qh].first==v.first-(i-cs/2))
				qu[qh].second-=v.second;
			qh+=!qu[qh].second;
		}
	}
	cout << ans.second;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5248 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 7 ms 5376 KB Output is correct
6 Correct 7 ms 5376 KB Output is correct
7 Correct 8 ms 5376 KB Output is correct
8 Correct 8 ms 5376 KB Output is correct
9 Correct 8 ms 5376 KB Output is correct
10 Correct 7 ms 5376 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 9592 KB Output is correct
2 Correct 62 ms 10104 KB Output is correct
3 Correct 43 ms 14452 KB Output is correct
4 Correct 39 ms 10104 KB Output is correct
5 Correct 41 ms 10108 KB Output is correct
6 Correct 148 ms 13728 KB Output is correct
7 Correct 98 ms 12168 KB Output is correct
8 Correct 77 ms 14968 KB Output is correct
9 Correct 79 ms 14964 KB Output is correct
10 Correct 75 ms 15864 KB Output is correct
11 Correct 114 ms 14952 KB Output is correct
12 Correct 124 ms 15468 KB Output is correct