oj.uz

Submission #116031

# Submission time Handle Problem Language Result Execution time Memory
116031 2019-06-10T08:50:37 Z ihdignite Shymbulak (IZhO14_shymbulak) C++14
100 / 100
 189 ms 18296 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 5 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 6 ms 4992 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 7 ms 4992 KB Output is correct
12 Correct 6 ms 5120 KB Output is correct
13 Correct 6 ms 5120 KB Output is correct
14 Correct 5 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 6 ms 5248 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 8 ms 5368 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 8 ms 5376 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 9720 KB Output is correct
2 Correct 59 ms 10112 KB Output is correct
3 Correct 44 ms 15604 KB Output is correct
4 Correct 39 ms 11256 KB Output is correct
5 Correct 44 ms 11312 KB Output is correct
6 Correct 189 ms 15964 KB Output is correct
7 Correct 118 ms 13944 KB Output is correct
8 Correct 78 ms 17520 KB Output is correct
9 Correct 83 ms 17528 KB Output is correct
10 Correct 74 ms 18296 KB Output is correct
11 Correct 93 ms 17256 KB Output is correct
12 Correct 120 ms 17896 KB Output is correct