oj.uz

답안 #411280

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411280 2021-05-24T22:22:47 Z penguinhacker 철인 이종 경기 (APIO18_duathlon) C++14
31 / 100
 101 ms 26592 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, m, tin[mxN], low[mxN], t, who[mxN], cc;
vector<int> adj1[mxN], adj2[mxN], cmp[mxN];
stack<int> st;
vector<ar<int, 2>> br;
ll n2, sz[mxN], ans, dp[mxN];

void make(int u) {
	while(cmp[cc].empty()||cmp[cc].back()^u) {
		cmp[cc].push_back(st.top());
		who[st.top()]=cc;
		st.pop();
	}
	sz[cc]=cmp[cc].size();
	++cc;
}

void dfs1(int u, int p=-1) {
	tin[u]=low[u]=++t;
	++n2;
	st.push(u);
	for (int v : adj1[u]) {
		if (v==p)
			continue;
		if (!tin[v]) {
			dfs1(v, u);
			low[u]=min(low[u], low[v]);
			if (low[v]>tin[u]) { //bridge
				br.push_back({u, v});
				make(v);
			}
		} else
			low[u]=min(low[u], tin[v]);
	}
}

void dfs2(int u) {
	dp[u]=sz[u];
	for (int v : adj2[u]) {
		dfs2(v);
		dp[u]+=dp[v];
		ans-=dp[v]*sz[u]*(dp[v]-1); // v->u->v
		ans-=2*dp[v]*(sz[u]-1);
		ans-=(n2-dp[v])*sz[v]*(n2-dp[v]-1); // u->v->u
		ans-=2*(n2-dp[v])*(sz[v]-1);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<m; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj1[u].push_back(v);
		adj1[v].push_back(u);
	}
	for (int i=0; i<n; ++i) {
		if (tin[i])
			continue;
		dfs1(i);
		make(i);
		while(br.size()) {
			ar<int, 2> a=br.back();
			br.pop_back();
			adj2[who[a[0]]].push_back(who[a[1]]);
		}
		ans+=n2*(n2-1)*(n2-2);
		dfs2(who[i]);
		n2=0;
	}
	cout << ans;
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 23332 KB Output is correct
2 Correct 62 ms 23252 KB Output is correct
3 Correct 85 ms 22088 KB Output is correct
4 Correct 73 ms 23208 KB Output is correct
5 Correct 65 ms 19132 KB Output is correct
6 Correct 72 ms 20996 KB Output is correct
7 Correct 82 ms 19956 KB Output is correct
8 Correct 79 ms 20932 KB Output is correct
9 Correct 69 ms 18804 KB Output is correct
10 Correct 70 ms 18948 KB Output is correct
11 Correct 67 ms 16836 KB Output is correct
12 Correct 74 ms 16708 KB Output is correct
13 Correct 60 ms 16916 KB Output is correct
14 Correct 56 ms 16712 KB Output is correct
15 Correct 50 ms 16708 KB Output is correct
16 Correct 63 ms 16428 KB Output is correct
17 Correct 14 ms 13252 KB Output is correct
18 Correct 14 ms 13220 KB Output is correct
19 Correct 14 ms 13176 KB Output is correct
20 Correct 14 ms 13132 KB Output is correct
21 Correct 14 ms 13172 KB Output is correct
22 Correct 14 ms 13140 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 7500 KB Output is correct
2 Correct 6 ms 7500 KB Output is correct
3 Correct 6 ms 7396 KB Output is correct
4 Correct 5 ms 7500 KB Output is correct
5 Correct 7 ms 7500 KB Output is correct
6 Correct 5 ms 7500 KB Output is correct
7 Correct 6 ms 7476 KB Output is correct
8 Correct 6 ms 7500 KB Output is correct
9 Correct 5 ms 7500 KB Output is correct
10 Correct 5 ms 7500 KB Output is correct
11 Correct 5 ms 7416 KB Output is correct
12 Correct 5 ms 7500 KB Output is correct
13 Correct 5 ms 7500 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7508 KB Output is correct
16 Correct 5 ms 7372 KB Output is correct
17 Correct 5 ms 7508 KB Output is correct
18 Correct 5 ms 7504 KB Output is correct
19 Correct 5 ms 7500 KB Output is correct
20 Correct 5 ms 7512 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 20124 KB Output is correct
2 Correct 79 ms 20016 KB Output is correct
3 Correct 100 ms 19996 KB Output is correct
4 Correct 72 ms 20020 KB Output is correct
5 Correct 79 ms 20112 KB Output is correct
6 Correct 90 ms 26592 KB Output is correct
7 Correct 97 ms 24136 KB Output is correct
8 Correct 85 ms 23132 KB Output is correct
9 Correct 80 ms 22180 KB Output is correct
10 Correct 84 ms 19856 KB Output is correct
11 Correct 94 ms 19912 KB Output is correct
12 Correct 75 ms 19520 KB Output is correct
13 Correct 75 ms 19540 KB Output is correct
14 Correct 72 ms 19052 KB Output is correct
15 Correct 76 ms 18776 KB Output is correct
16 Correct 48 ms 17424 KB Output is correct
17 Correct 51 ms 19576 KB Output is correct
18 Correct 57 ms 19384 KB Output is correct
19 Correct 74 ms 19440 KB Output is correct
20 Correct 56 ms 19316 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 20032 KB Output is correct
2 Correct 86 ms 20328 KB Output is correct
3 Incorrect 101 ms 18060 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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