oj.uz

답안 #252443

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
252443 2020-07-25T15:25:03 Z amoo_safar 철인 이종 경기 (APIO18_duathlon) C++14
0 / 100
 409 ms 226796 KB 
#include<bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define debug(x) cerr << #x << " = " << x << '\n'

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 10;
const int N2 = N * 8;

ll ans;
int n, m;

int la;
vector<int> H[N], G[N2], R[N2];

int mk[N2], st[N], T = 1, dep[N2], wh[N];

void AddEdge(int u, int v){
	G[u].pb(v);
	G[v].pb(u);
	//cerr << u << ' ' << v << '\n';
}

int dfs(int u, int p, int d){
	mk[u] = 1;
	dep[u] = d;
	st[u] = T ++;

	int hbk = d, res;
	int cnt = (p == -1 ? 0 : 1);
	
	vector<pii> V;

	for(auto adj : H[u]){
		if(adj == p) continue;
		if(mk[adj]){
			hbk = min(hbk, dep[adj]);
		} else {
			res = dfs(adj, u, d + 1);
			hbk = min(hbk, res);
			if(res >= d){
				cnt ++;
				V.pb({T, cnt});
			} else {
				V.pb({T, 1});
			}

		}
	}
	//cerr << "! " << u << ' ' << cnt << ' ' << la << '\n';
	if(cnt > 0){
		wh[u] = la + 1;
		for(int i = 1; i <= cnt; i++) AddEdge(u, la + i);
		int idx;
		for(auto adj : H[u]){
			if(dep[adj] < dep[u]) idx = 1;
			else idx = upper_bound(V.begin(), V.end(), pii(st[adj], cnt + 1)) -> S;
			if(dep[adj] >= dep[u]) AddEdge(wh[adj], la + idx);
		}
		la += cnt;
	} else {
		assert(0);
	}
	return hbk;
}

int par[N2], sz[N];
int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
void Unite(int u, int v){
	u = Find(u); v = Find(v);
	if(u == v) return ;
	par[u] = v;
	sz[v] += sz[u];
}

vector<pii> cut;
int DFS(int u, int p, int d){
	mk[u] = 1;
	dep[u] = d;

	int hbk = d, res;
	for(auto adj : G[u]){
		if(adj == p) continue;
		if(mk[adj]){
			hbk = min(hbk, dep[adj]);
			Unite(u, adj);
		} else {
			res = DFS(adj, u, d + 1);
			hbk = min(res, hbk);
			if(res <= d) Unite(adj, u);
			else {
				cut.pb(pii(adj, u));
			}
		}
	}
	return hbk;
}
int sub[N2];
vector<int> vis;
vector<pii> oth;
void DFS2(int u, int p, int d){
	vis.pb(u);
	sub[u] = sz[u];
	dep[u] = d;
	mk[u] = 1;
	for(auto adj : R[u]){
		if(adj == p) continue;
		DFS2(adj, u, d + 1);
		sub[u] += sub[adj];
	}
}

vector<int> com[N2];
vector<int> fuck[N2];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	int u, v;
	for(int i = 1; i <= m; i++){
		cin >> u >> v;
		H[u].pb(v);
		H[v].pb(u);
	}

	cerr << '\n';
	
	la = n;
	for(int i = 1; i <= n; i++){
		if(mk[i]) continue;
		dfs(i, -1, 0);
	}
	iota(par, par + N2, 0);
	fill(sz + 1, sz + n + 1, 1);

	memset(mk, 0, sizeof mk);
	for(int i = 1; i <= la; i++){
		if(mk[i]) continue;
		DFS(i, -1, 0);
	}
	for(int i = 1; i <= la; i++) com[Find(i)].pb(i);

	for(auto &x : cut){
		x.F = Find(x.F); x.S = Find(x.S);
		R[x.F].pb(x.S);
		R[x.S].pb(x.F);
	}

	memset(mk, 0, sizeof mk);
	
	for(int i = 1; i <= la; i++){
		if(mk[i]) continue;
		if(Find(i) != i) continue;
		vis.clear();
		DFS2(i, -1, 0);


		int sm = sub[i];
		for(auto nd : vis){
			oth.clear();
			vector<int> con;
			for(auto nd2 : com[nd]){
				int res = (nd2 <= n), res2 = 0, tmp;
				
				vector<pii> ed;
				for(auto adj : G[nd2]){
					if(Find(adj) == nd) continue;
					int tm;
					tmp = Find(adj);
					if(dep[tmp] > dep[nd]) tm = sub[tmp];
					else tm = sm - sub[nd];
					ed.pb({tm, adj});
					res += tm;
					res2 += tm;
				}
				ll S2 = 0;
				for(auto [tm, adj] : ed) S2 += (tm) * (tm - 1); 
				bool fl = false;
				for(auto [tm, adj] : ed){
					if((adj <= n) && (wh[adj] != adj)){
						fuck[adj].pb(sm - tm);
						//if(nd2 <= n) tm --;
						ans += 1ll * (res2 - tm) * (res2 - tm - 1);
						ans -= S2 - (tm * (tm - 1));

						ans += 2ll * (sm - res) * (res2 - tm);
						fl = true;
					}
				}
				oth.pb({res, fl});
			}
			ll Sum = 0, S2 = 0;
			for(auto [res, fl] : oth){
				Sum += res;
				S2 += res * (res - 1);
			}
			for(auto [res, fl] : oth){
				if(fl){
					ans += 1ll * (Sum - res) * (Sum - res - 1);
					ans -= S2 - (1ll * (res) * (res - 1));
				}
			}
				
		}
	}
	ans = 0;
	for(int i = 1; i <= n; i++){
		if(wh[i] == i) continue;

		int sm = 0;
		for(auto x : fuck[i]){
			sm += x;
			ans -= 1ll * x * (x - 1);
		}
		ans += 1ll * sm * (sm - 1);
	}
	cout << ans << '\n';
	return 0;
}
/*
9 10
1 2
2 3
3 4
4 5
4 2
3 6
6 7
6 8
8 3
8 9


10 9
1 2
2 3
*/

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:186:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [tm, adj] : ed) S2 += (tm) * (tm - 1); 
              ^
count_triplets.cpp:186:22: warning: unused variable 'adj' [-Wunused-variable]
     for(auto [tm, adj] : ed) S2 += (tm) * (tm - 1); 
                      ^
count_triplets.cpp:188:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for(auto [tm, adj] : ed){
              ^
count_triplets.cpp:202:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [res, fl] : oth){
             ^
count_triplets.cpp:202:21: warning: unused variable 'fl' [-Wunused-variable]
    for(auto [res, fl] : oth){
                     ^
count_triplets.cpp:206:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
    for(auto [res, fl] : oth){
             ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 124 ms 157560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 124 ms 157560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 279 ms 226796 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 84600 KB Output is correct
2 Correct 49 ms 84616 KB Output is correct
3 Correct 49 ms 84600 KB Output is correct
4 Correct 51 ms 84872 KB Output is correct
5 Correct 49 ms 84728 KB Output is correct
6 Correct 49 ms 84600 KB Output is correct
7 Correct 50 ms 84728 KB Output is correct
8 Correct 50 ms 84600 KB Output is correct
9 Correct 50 ms 84600 KB Output is correct
10 Correct 50 ms 84600 KB Output is correct
11 Correct 50 ms 84600 KB Output is correct
12 Correct 54 ms 84720 KB Output is correct
13 Correct 50 ms 84600 KB Output is correct
14 Runtime error 136 ms 157764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 409 ms 126044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 84604 KB Output is correct
2 Correct 48 ms 84600 KB Output is correct
3 Incorrect 49 ms 84472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 400 ms 126172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 124 ms 157560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 124 ms 157560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -