oj.uz

Submission #50029

# Submission time Handle Problem Language Result Execution time Memory
50029 2018-06-06T14:11:53 Z tmwilliamlin168 Duathlon (APIO18_duathlon) C++14
0 / 100
 302 ms 53632 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second

const int mxN=1e5;
int n, m, dt=1, tin[mxN], low[mxN], sth, bccI;
pii st[2*mxN];
ll sz1[2*mxN], sz2[mxN], ans;
vector<int> adj1[mxN], adj2[2*mxN];
set<int> bccs[mxN];
bool vis[2*mxN];

void dfs1(int u, int p) {
	tin[u]=low[u]=dt++;
	for(int v : adj1[u]) {
		if(!tin[v]) {
			int lsth=sth;
			st[sth++]={u, v};
			dfs1(v, u);
			low[u]=min(low[v], low[u]);
			if(low[v]>=tin[u]) {
				while(sth>lsth) {
					--sth;
					bccs[bccI].insert(st[sth].fi);
					bccs[bccI].insert(st[sth].se);
				}
				++bccI;
			}
		} else if(v!=p)
			low[u]=min(tin[v], low[u]);
	}
}

void dfs2(int u, int p) {
//	cout << "d2 " << u << endl;
	vis[u]=1;
	sz1[u]=u<n;
	ll n2=n-adj2[u].size();
	for(int v : adj2[u]) {
		if(v==p)
			continue;
		dfs2(v, u);
		sz1[u]+=sz1[v];
		n2-=sz1[v]-1;
		if(u>=n)
			ans+=2*(sz1[v]-sz2[v]+adj2[u].size()-2)*n2;
	}
	if(u<n) {
		n2=sz1[u]-sz2[u]+adj2[p].size()-2;
		for(int v : adj2[u]) {
			if(v==p)
				continue;
			n2-=sz1[v]-adj2[v].size()+1;
			ans+=2*(sz1[v]-adj2[v].size()+1)*n2;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	while(m--) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj1[u].push_back(v);
		adj1[v].push_back(u);
	}
	dfs1(0, -1);
	for(int i=0; i<bccI; ++i) {
		ll bs=bccs[i].size();
		for(int j : bccs[i]) {
			adj2[j].push_back(i+n);
			adj2[i+n].push_back(j);
			sz2[j]+=bs-1;
		}
		ans+=bs*(bs-1)*(bs-2)+2*(bs-1)*(bs-1)*(n-bs)+bs*(bs-1)*(bs-1);
	}
	for(int i=0; i<n; ++i)
		ans-=sz2[i]*sz2[i];
//	cout << bccI << " " << ans << endl;
//	for(int i=0; i<n; ++i)
//		cout << sz2[i] << " ";
//	cout << endl;
	for(int i=0; i<bccI; ++i)
		if(!vis[i+n])
			dfs2(i+n, -1);
	cout << ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 34548 KB Output is correct
2 Correct 172 ms 34592 KB Output is correct
3 Incorrect 122 ms 34592 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 34592 KB Output is correct
2 Correct 13 ms 34592 KB Output is correct
3 Correct 16 ms 34592 KB Output is correct
4 Correct 13 ms 34592 KB Output is correct
5 Correct 14 ms 34592 KB Output is correct
6 Correct 14 ms 34592 KB Output is correct
7 Correct 13 ms 34592 KB Output is correct
8 Correct 13 ms 34592 KB Output is correct
9 Correct 14 ms 34592 KB Output is correct
10 Incorrect 13 ms 34592 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 34812 KB Output is correct
2 Correct 183 ms 34812 KB Output is correct
3 Correct 207 ms 34928 KB Output is correct
4 Correct 229 ms 34928 KB Output is correct
5 Correct 206 ms 34928 KB Output is correct
6 Correct 236 ms 53632 KB Output is correct
7 Correct 253 ms 53632 KB Output is correct
8 Correct 249 ms 53632 KB Output is correct
9 Correct 248 ms 53632 KB Output is correct
10 Incorrect 169 ms 53632 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 53632 KB Output is correct
2 Correct 13 ms 53632 KB Output is correct
3 Incorrect 13 ms 53632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 53632 KB Output is correct
2 Correct 302 ms 53632 KB Output is correct
3 Incorrect 244 ms 53632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12024 KB Output isn't correct
2 Halted 0 ms 0 KB -