oj.uz

Submission #116026

# Submission time Handle Problem Language Result Execution time Memory
116026 2019-06-10T08:42:17 Z ihdignite Shymbulak (IZhO14_shymbulak) C++14
0 / 100
 65 ms 11260 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&&qu[qt-1].first<u.first-i)
			--qt;
		if(!qt||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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 5 ms 5120 KB Output is correct
3 Correct 7 ms 5248 KB Output is correct
4 Correct 5 ms 5092 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 5 ms 4992 KB Output is correct
9 Correct 6 ms 5120 KB Output is correct
10 Incorrect 6 ms 5120 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 5 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 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 Incorrect 8 ms 5376 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 10732 KB Output is correct
2 Incorrect 64 ms 11260 KB Output isn't correct
3 Halted 0 ms 0 KB -