oj.uz

Submission #728613

# Submission time Handle Problem Language Result Execution time Memory
728613 2023-04-22T17:46:29 Z myrcella Duathlon (APIO18_duathlon) C++17
0 / 100
 88 ms 31728 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];
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];
	}
	if (u<=n) {
		ll cnt = 0;
		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];
		}
	}
	else {
		ll cnt = 0;
		for (int v:tree[u]) {
			if (v==fa) continue;
			dpp[u] += cnt*dp[v][0];
			cnt += dp[v][0];
			dpp[u] += 2*(SZ(tree[u])-2)*dp[v][0];
		}
	}
}

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 6 ms 11304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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