oj.uz

Submission #403740

# Submission time Handle Problem Language Result Execution time Memory
403740 2021-05-13T11:59:02 Z Bill_00 Duathlon (APIO18_duathlon) C++14
0 / 100
 245 ms 44228 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define ll long long
#define N 100005
using namespace std;
ll n, m, timer, ans;
ll low[N], tin[N], p[N], sz[N], newsz[N];
vector<ll> adj[N], newadj[N];
unordered_map<ll, bool> bridge[N];
bool vis[N];
void dfs(ll v, ll p = -1) {
    vis[v] = 1;
    tin[v] = low[v] = timer++;
    for (ll to : adj[v]) {
        if(to == p) continue;
        if(vis[to]){
            low[v] = min(low[v], tin[to]);
        } 
        else{
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if(low[to] > tin[v]){
            	bridge[v][to]=1;
            	bridge[to][v]=1;
            }
        }
    }
}
void dfs1(ll node, ll head=1){
	sz[head]++;
	p[node]=head;
	vis[node]=1;
	for(ll to : adj[node]) {
		if(!vis[to]) {
			if(bridge[node][to]) {
				dfs1(to, to);
				newadj[head].pb(to);
				newadj[to].pb(head);
			}
			else dfs1(to, head);
		}
	}
}
void solve(ll node, ll par=-1){
	// cout << node << ' ' << sz[node] << '\n';
	ll sum=0, res=0;
	ans+=(sz[node]*(sz[node]-1)*(sz[node]-2));
	newsz[node]=sz[node];
	for(ll to : newadj[node]){
		if(par != to) {
			solve(to, node);
			newsz[node]+=newsz[to];
			sum+=newsz[to];
			res+=(newsz[to]*newsz[to]);
			ans+=((sz[node]-1)*(sz[node]-2)*newsz[to]*2+newsz[to]*(sz[node]-1)*2);
		}
	}
	ans+=((sz[node]-1)*(sz[node]-2)*(n-newsz[node])*2+(n-newsz[node])*(sz[node]-1)*2);
	ans+=((newsz[node]-sz[node])*(n-newsz[node])*2);
	ans+=(sum*sum-res); 
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(ll i=1;i<=m;i++){
		ll u,v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(1);
	memset(vis,0,sizeof(vis));
	dfs1(1);
	solve(1);
	cout << ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 40692 KB Output is correct
2 Correct 156 ms 40756 KB Output is correct
3 Incorrect 84 ms 28944 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10892 KB Output is correct
2 Correct 9 ms 10828 KB Output is correct
3 Correct 8 ms 10828 KB Output is correct
4 Correct 8 ms 10960 KB Output is correct
5 Correct 9 ms 10900 KB Output is correct
6 Correct 9 ms 10828 KB Output is correct
7 Correct 9 ms 10828 KB Output is correct
8 Correct 9 ms 10872 KB Output is correct
9 Correct 9 ms 10828 KB Output is correct
10 Incorrect 8 ms 10632 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 40428 KB Output is correct
2 Correct 197 ms 40428 KB Output is correct
3 Correct 199 ms 40404 KB Output is correct
4 Correct 226 ms 40396 KB Output is correct
5 Correct 193 ms 40516 KB Output is correct
6 Correct 209 ms 44228 KB Output is correct
7 Correct 210 ms 43404 KB Output is correct
8 Correct 245 ms 42508 KB Output is correct
9 Correct 236 ms 41776 KB Output is correct
10 Incorrect 149 ms 31296 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10828 KB Output is correct
2 Correct 9 ms 10828 KB Output is correct
3 Incorrect 8 ms 10760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 40316 KB Output is correct
2 Correct 219 ms 40188 KB Output is correct
3 Incorrect 195 ms 37008 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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