oj.uz

답안 #403755

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403755 2021-05-13T12:09:49 Z Bill_00 철인 이종 경기 (APIO18_duathlon) C++14
31 / 100
 230 ms 43060 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, nn, m, timer, ans;
ll low[N], tin[N], p[N], sz[N], newsz[N], compsz[N];
vector<ll> adj[N], newadj[N];
unordered_map<ll, bool> bridge[N];
bool vis[N], mark[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){
	nn++;
	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';
	vis[node]=1;
	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)*(nn-newsz[node])*2+(nn-newsz[node])*(sz[node]-1)*2);
	ans+=((newsz[node]-sz[node])*(nn-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);
	}
	for(ll i=1;i<=n;i++){
		if(vis[i]==0) dfs(i);
	}
	memset(vis,0,sizeof(vis));
	for(ll i=1;i<=n;i++){
		if(vis[i]==0){
			nn=0;
			dfs1(i,i);
			compsz[i]=nn;
			mark[i]=1;
		} 
	}
	memset(vis,0,sizeof(vis));
	for(ll i=1;i<=n;i++){
		if(mark[i]==1){
			nn=compsz[i];
			solve(i);
		}
	}
	cout << ans;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 10572 KB Output is correct
2 Correct 7 ms 10628 KB Output is correct
3 Correct 7 ms 10628 KB Output is correct
4 Correct 7 ms 10572 KB Output is correct
5 Correct 7 ms 10632 KB Output is correct
6 Correct 8 ms 10624 KB Output is correct
7 Incorrect 7 ms 10632 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 10572 KB Output is correct
2 Correct 7 ms 10628 KB Output is correct
3 Correct 7 ms 10628 KB Output is correct
4 Correct 7 ms 10572 KB Output is correct
5 Correct 7 ms 10632 KB Output is correct
6 Correct 8 ms 10624 KB Output is correct
7 Incorrect 7 ms 10632 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 39488 KB Output is correct
2 Correct 130 ms 39528 KB Output is correct
3 Correct 151 ms 39480 KB Output is correct
4 Correct 145 ms 41540 KB Output is correct
5 Correct 135 ms 38188 KB Output is correct
6 Correct 154 ms 39484 KB Output is correct
7 Correct 177 ms 38596 KB Output is correct
8 Correct 160 ms 39236 KB Output is correct
9 Correct 156 ms 37664 KB Output is correct
10 Correct 174 ms 37780 KB Output is correct
11 Correct 141 ms 34416 KB Output is correct
12 Correct 128 ms 34116 KB Output is correct
13 Correct 134 ms 33808 KB Output is correct
14 Correct 128 ms 33304 KB Output is correct
15 Correct 100 ms 31444 KB Output is correct
16 Correct 100 ms 30548 KB Output is correct
17 Correct 13 ms 15440 KB Output is correct
18 Correct 13 ms 15436 KB Output is correct
19 Correct 13 ms 15444 KB Output is correct
20 Correct 12 ms 15436 KB Output is correct
21 Correct 13 ms 15408 KB Output is correct
22 Correct 12 ms 15364 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 10828 KB Output is correct
2 Correct 9 ms 10876 KB Output is correct
3 Correct 9 ms 10828 KB Output is correct
4 Correct 9 ms 10956 KB Output is correct
5 Correct 8 ms 10856 KB Output is correct
6 Correct 8 ms 10828 KB Output is correct
7 Correct 8 ms 10828 KB Output is correct
8 Correct 8 ms 10828 KB Output is correct
9 Correct 8 ms 10900 KB Output is correct
10 Correct 9 ms 10888 KB Output is correct
11 Correct 8 ms 10828 KB Output is correct
12 Correct 9 ms 10828 KB Output is correct
13 Correct 8 ms 10892 KB Output is correct
14 Correct 10 ms 10828 KB Output is correct
15 Correct 8 ms 10828 KB Output is correct
16 Correct 8 ms 10756 KB Output is correct
17 Correct 8 ms 10828 KB Output is correct
18 Correct 8 ms 10844 KB Output is correct
19 Correct 8 ms 10956 KB Output is correct
20 Correct 9 ms 10892 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 39148 KB Output is correct
2 Correct 198 ms 39252 KB Output is correct
3 Correct 230 ms 39136 KB Output is correct
4 Correct 181 ms 39208 KB Output is correct
5 Correct 186 ms 39200 KB Output is correct
6 Correct 178 ms 43060 KB Output is correct
7 Correct 193 ms 42264 KB Output is correct
8 Correct 193 ms 41344 KB Output is correct
9 Correct 201 ms 40552 KB Output is correct
10 Correct 181 ms 39108 KB Output is correct
11 Correct 220 ms 40380 KB Output is correct
12 Correct 177 ms 40448 KB Output is correct
13 Correct 191 ms 40424 KB Output is correct
14 Correct 183 ms 40052 KB Output is correct
15 Correct 157 ms 38412 KB Output is correct
16 Correct 112 ms 32216 KB Output is correct
17 Correct 169 ms 42148 KB Output is correct
18 Correct 169 ms 42156 KB Output is correct
19 Correct 166 ms 42184 KB Output is correct
20 Correct 161 ms 41852 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 10828 KB Output is correct
2 Correct 8 ms 10876 KB Output is correct
3 Incorrect 8 ms 10876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 39292 KB Output is correct
2 Correct 183 ms 38956 KB Output is correct
3 Incorrect 188 ms 35476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 10572 KB Output is correct
2 Correct 7 ms 10628 KB Output is correct
3 Correct 7 ms 10628 KB Output is correct
4 Correct 7 ms 10572 KB Output is correct
5 Correct 7 ms 10632 KB Output is correct
6 Correct 8 ms 10624 KB Output is correct
7 Incorrect 7 ms 10632 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 10572 KB Output is correct
2 Correct 7 ms 10628 KB Output is correct
3 Correct 7 ms 10628 KB Output is correct
4 Correct 7 ms 10572 KB Output is correct
5 Correct 7 ms 10632 KB Output is correct
6 Correct 8 ms 10624 KB Output is correct
7 Incorrect 7 ms 10632 KB Output isn't correct
8 Halted 0 ms 0 KB -