oj.uz

Submission #50025

# Submission time Handle Problem Language Result Execution time Memory
50025 2018-06-06T13:19:12 Z tmwilliamlin168 Duathlon (APIO18_duathlon) C++14
0 / 100
 238 ms 34620 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) {
//	cout << "d2 " << u << endl;
	vis[u]=1;
	sz1[u]=u<n;
	for(int v : adj2[u]) {
		if(vis[v])
			continue;
		dfs2(v);
		sz1[u]+=sz1[v];
		if(u>=n)
			ans+=(ll)(sz1[v]-sz2[v]+adj2[u].size()-2)*(n-sz1[v]-adj2[u].size()+1);
	}
}

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);
	cout << ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12152 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 12152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 34620 KB Output is correct
2 Correct 238 ms 34620 KB Output is correct
3 Incorrect 134 ms 34620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12152 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 12152 KB Output isn't correct
2 Halted 0 ms 0 KB -