oj.uz

답안 #714474

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
714474 2023-03-24T15:25:25 Z radal 철인 이종 경기 (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048576 KB 
#include <bits/stdc++.h>
//#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O3")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 2e5+20,mod = 998244353;
constexpr ll inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}

int n,m;
int h[N],mi[N];
bool cut[N];
int mark[N],sz[N],sum[N];
vector<int> G[N],cp,adj[N];
ll ans;

void dfs(int v){
	cp.pb(v);
	mi[v] = h[v];
	int deg = 0;
	for (int u : G[v]){

		if (h[u] != -1){
			mi[v] = min(mi[v],h[u]);
		   	continue;
		}
		deg++;
		h[u] = h[v] + 1;
		dfs(u);
		if (mi[u] >= h[v] && h[v]) cut[v] = 1;
	}
	if (!h[v] && deg > 1) cut[v] = 1;
}

void dfs2(int v,int c){
	if (cut[v]){
		adj[v].pb(c);
		adj[c].pb(v);
		return;
	}
	mark[v] = c;
	sz[c]++;
	for (int u : G[v]){
		if (!mark[u])
			dfs2(u,c);
	}
}

void dfs3(int v,int p){
	sort(all(adj[v]));
	adj[v].resize(unique(all(adj[v]))-adj[v].begin());
	int s;
	if (v > n) s = sz[v];
	else s = 1;
	sum[v] = s;
	if (v > n){
		int x = adj[v].size();
		ans += 1ll*s*(s-1)*(s-2);
		ans += 1ll*x*s*(s-1);
		ans += 2ll*x*(x-1)*s;
		ans += 1ll*x*(x-1)*(x-2);
	}
	for (int u : adj[v]){
		if (u == p) continue;
		dfs3(u,v);
		ans += 1ll*s*sum[u]*(cp.size()-1-sum[u]);
		ans += 1ll*s*(s-1)*sum[u];
		sum[v] += sum[u];
	}

	ans += 1ll*s*(cp.size()-sum[v])*(sum[v]-1);
	ans += 1ll*s*(s-1)*(cp.size()-sum[v]);
}
int main(){
	ios :: sync_with_stdio(0); cin.tie(0);  cout.tie(0);
	memset(h,-1,sizeof h);
	cin >> n >> m;
	rep(i,0,m){
		int u,v;
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	int cur = n+1;
	rep(i,1,n+1){
		if (h[i] != -1) continue;
		cp.clear();
		h[i] = 0;
		dfs(i);
		if ((int)cp.size() < 3) continue;

		int tedb = 0;
		for (int v : cp){
			if (cut[v]){
				for (int u : G[v]) if (cut[u]) adj[v].pb(u);
				continue;
			}
			if (mark[v]) continue;
			dfs2(v,cur);
			cur++;
			tedb++;
		}
		if (tedb) dfs3(cur-1,-1);
		else dfs3(cp.back(),-1);
	}
	cout << ans << endl;

}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10464 KB Output is correct
5 Correct 8 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Runtime error 852 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10464 KB Output is correct
5 Correct 8 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Runtime error 852 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1058 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 10580 KB Output is correct
2 Correct 7 ms 10508 KB Output is correct
3 Correct 8 ms 10580 KB Output is correct
4 Correct 6 ms 10636 KB Output is correct
5 Correct 6 ms 10664 KB Output is correct
6 Correct 8 ms 10580 KB Output is correct
7 Correct 7 ms 10708 KB Output is correct
8 Correct 6 ms 10580 KB Output is correct
9 Correct 8 ms 10580 KB Output is correct
10 Correct 6 ms 10580 KB Output is correct
11 Correct 7 ms 10580 KB Output is correct
12 Correct 8 ms 10580 KB Output is correct
13 Correct 6 ms 10564 KB Output is correct
14 Correct 7 ms 10512 KB Output is correct
15 Correct 7 ms 10580 KB Output is correct
16 Correct 9 ms 10580 KB Output is correct
17 Correct 9 ms 10580 KB Output is correct
18 Correct 9 ms 10552 KB Output is correct
19 Correct 6 ms 10580 KB Output is correct
20 Correct 7 ms 10532 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 18924 KB Output is correct
2 Correct 80 ms 20332 KB Output is correct
3 Correct 96 ms 20288 KB Output is correct
4 Correct 98 ms 20296 KB Output is correct
5 Correct 92 ms 20292 KB Output is correct
6 Correct 121 ms 30240 KB Output is correct
7 Correct 119 ms 23816 KB Output is correct
8 Correct 89 ms 22812 KB Output is correct
9 Correct 116 ms 21904 KB Output is correct
10 Correct 82 ms 20124 KB Output is correct
11 Correct 90 ms 20188 KB Output is correct
12 Correct 109 ms 19976 KB Output is correct
13 Correct 73 ms 19992 KB Output is correct
14 Correct 75 ms 19404 KB Output is correct
15 Correct 68 ms 19032 KB Output is correct
16 Correct 49 ms 16544 KB Output is correct
17 Correct 52 ms 20764 KB Output is correct
18 Correct 54 ms 20672 KB Output is correct
19 Correct 58 ms 20932 KB Output is correct
20 Correct 68 ms 20752 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 10580 KB Output is correct
2 Correct 7 ms 10580 KB Output is correct
3 Runtime error 764 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 18964 KB Output is correct
2 Correct 90 ms 20112 KB Output is correct
3 Execution timed out 1012 ms 1048576 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10464 KB Output is correct
5 Correct 8 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Runtime error 852 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10452 KB Output is correct
2 Correct 5 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10464 KB Output is correct
5 Correct 8 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Runtime error 852 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -