oj.uz

Submission #728641

# Submission time Handle Problem Language Result Execution time Memory
728641 2023-04-22T18:25:19 Z myrcella Duathlon (APIO18_duathlon) C++17
23 / 100
 139 ms 38396 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 200010;

int n,m;
vector <int> edge[maxn];
vector <int> tree[maxn];
ll dp[maxn][2],dpp[maxn][2];
int dfn[maxn],low[maxn];
int tot = 0,cnt;
ll ans = 0;
stack <int> s;

void solve(int u,int fa) {
	dfn[u] = 1;
	if (u<=n) dp[u][0]++;
	for (int v:tree[u]) {
		if (v==fa) continue;
//		debug(u),debug(v);
		solve(v,u);
		dp[u][0] += dp[v][0];
		dp[u][1] += dp[v][1];
		if (u<=n) dp[u][1] += dp[v][0];
		dpp[u][0] += dpp[v][0];
	}
	if (u<=n) {
		ll cnt = 0;
//		debug(u),debug(ans);
		for (int v:tree[u]) {
			if (v==fa) continue;
			ans += cnt*dp[v][0];
			cnt += dp[v][0];
			ans += dp[v][1];
			ans += dpp[v][0] + dpp[v][1];
//			debug(dp[v][0]),debug(dp[v][1]);
		}
//		debug(ans);
	}
	else {
		ll cnt = 0;
		for (int v:tree[u]) {
			if (v==fa) continue;
			dpp[u][1] += cnt*dp[v][0];
			cnt += dp[v][0];
			dpp[u][0] += (SZ(tree[u])-2)*dp[v][0];
		}
	}
	ll cnt1=0,cnt2=0;
	for (int v:tree[u]) {
		if (v==fa) continue;
		ans += cnt1*dp[v][1] + cnt2*dp[v][0];
		cnt1 += dp[v][0], cnt2 += dp[v][1];
	}
}

void tarjan(int u,int fa) {
	dfn[u] = low[u] = tot++;
	s.push(u);
	for (int v:edge[u]) {
		if (v==fa) continue;
		if (dfn[v]==-1) {
			tarjan(v,u);
			low[u] = min(low[u],low[v]);
//			cout<<u<<" "<<v<<" "<<dfn[u]<<" "<<low[v]<<endl;
			if (low[v]>=dfn[u]) {
				while (1) {
					int cur = s.top();
					s.pop();
					tree[cnt].pb(cur);
					tree[cur].pb(cnt);
					if (cur==v) break;
				}
				tree[cnt].pb(u);
				tree[u].pb(cnt);
				cnt++;
			}
			
		}
		else low[u] = min(low[u],dfn[v]);
	}
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	memset(low,-1,sizeof(low));
	memset(dfn,-1,sizeof(dfn));
	cin>>n>>m;
	cnt=n+1;
	rep(i,0,m) {
		int u,v;
		cin>>u>>v;
		edge[u].pb(v);
		edge[v].pb(u);
	}
	rep(i,1,n+1) if (dfn[i]==-1) tarjan(i,-1);
	memset(dfn,-1,sizeof(dfn));
	rep(i,1,n+1) if (dfn[i]==-1) solve(i,-1);
	cout<<2*ans;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 11220 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 11220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11424 KB Output is correct
2 Correct 7 ms 11428 KB Output is correct
3 Correct 7 ms 11376 KB Output is correct
4 Correct 7 ms 11604 KB Output is correct
5 Correct 7 ms 11556 KB Output is correct
6 Correct 7 ms 11428 KB Output is correct
7 Correct 6 ms 11476 KB Output is correct
8 Correct 7 ms 11476 KB Output is correct
9 Correct 7 ms 11476 KB Output is correct
10 Correct 7 ms 11388 KB Output is correct
11 Correct 7 ms 11428 KB Output is correct
12 Correct 9 ms 11360 KB Output is correct
13 Correct 7 ms 11348 KB Output is correct
14 Correct 10 ms 11348 KB Output is correct
15 Correct 7 ms 11348 KB Output is correct
16 Correct 6 ms 11348 KB Output is correct
17 Correct 7 ms 11348 KB Output is correct
18 Correct 6 ms 11476 KB Output is correct
19 Correct 7 ms 11476 KB Output is correct
20 Correct 8 ms 11388 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 27516 KB Output is correct
2 Correct 114 ms 28332 KB Output is correct
3 Correct 94 ms 28320 KB Output is correct
4 Correct 96 ms 28356 KB Output is correct
5 Correct 105 ms 28360 KB Output is correct
6 Correct 119 ms 38396 KB Output is correct
7 Correct 139 ms 34940 KB Output is correct
8 Correct 127 ms 33184 KB Output is correct
9 Correct 106 ms 31512 KB Output is correct
10 Correct 112 ms 28332 KB Output is correct
11 Correct 111 ms 28276 KB Output is correct
12 Correct 114 ms 28412 KB Output is correct
13 Correct 123 ms 28360 KB Output is correct
14 Correct 83 ms 27500 KB Output is correct
15 Correct 94 ms 26532 KB Output is correct
16 Correct 52 ms 23036 KB Output is correct
17 Correct 82 ms 27416 KB Output is correct
18 Correct 72 ms 27332 KB Output is correct
19 Correct 73 ms 27408 KB Output is correct
20 Correct 68 ms 27428 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11348 KB Output is correct
2 Correct 6 ms 11424 KB Output is correct
3 Incorrect 7 ms 11348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 27384 KB Output is correct
2 Correct 94 ms 28252 KB Output is correct
3 Incorrect 102 ms 27412 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 11220 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 11220 KB Output isn't correct
2 Halted 0 ms 0 KB -