oj.uz

Submission #395155

# Submission time Handle Problem Language Result Execution time Memory
395155 2021-04-27T23:03:53 Z CSQ31 Duathlon (APIO18_duathlon) C++14
0 / 100
 203 ms 31240 KB 
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN  = 2e5+5;
int n,n2,timer = 0;
vector<int>low(MAXN),tin(MAXN),sub(MAXN);
vii g(MAXN),g2(MAXN);
stack<int>stk;
ll ans = 0,cnt = 0;
void bbc(int v,int u){
	cnt++;
	tin[v] = low[v] = ++timer;
	stk.push(v);
	for(int x:g[v]){
		if(x!= u){
			if(!tin[x]){
				bbc(x,v);
				low[v] = min(low[v],low[x]);
				if(low[x] >= tin[v]){
					n2++;
					g2[v].pb(n2);
					g2[n2].pb(v);
					while(g2[n2].back() != x){
						g2[n2].pb(stk.top());
						g2[stk.top()].pb(n2);
						stk.pop();
					}
				}
			}else{
				low[v] = min(low[v],tin[x]);	
			}
		}
	}
}
void dfs(int v,int u){
	sub[v] = (v<=n);
	for(int x:g2[v]){
		if(x != u){
			dfs(x,v);
			sub[v]+=sub[x];
		}
	}
}
void dfs2(int v,int u){
	for(int x:g2[v]){
		if(x != u){
			dfs2(x,v);//c is in this bbc
		    if(v > n)ans-=(sz(g2[v]) - 1) * 1LL * sub[x] * 1LL *(sub[x]-1); //s and f is under this art vertex
		}
	}
	if(v > n)ans-=(sz(g2[v])-1) * 1LL * (n-sub[v]) * 1LL * (n-sub[v]-1); //try parent as art vertex
}
int main()
{
	int m;
	cin>>n>>m;
	n2 = n;
	for(int i=0;i<m;i++){
		int v,u;
		cin>>v>>u;
		g[v].pb(u);
		g[u].pb(v);
	}
	for(int i=1;i<=n;i++){
		if(!tin[i]){
			cnt = 0;
			bbc(i,-1);
			dfs(i,-1);
			//for(int i=1;i<=n2;i++)cout<<sub[i]<<" ";
	        dfs2(i,-1);
			ans+=cnt*(cnt-1)*(cnt-2);

		}
	}

	cout<<ans<<'\n';
	
}

Subtask #1
0 / 5.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 27836 KB Output is correct
2 Correct 128 ms 27776 KB Output is correct
3 Incorrect 176 ms 27776 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12108 KB Output is correct
2 Correct 8 ms 12108 KB Output is correct
3 Correct 8 ms 12108 KB Output is correct
4 Correct 8 ms 12236 KB Output is correct
5 Correct 8 ms 12236 KB Output is correct
6 Correct 8 ms 12192 KB Output is correct
7 Correct 7 ms 12236 KB Output is correct
8 Correct 7 ms 12108 KB Output is correct
9 Correct 7 ms 12108 KB Output is correct
10 Incorrect 8 ms 12108 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 22852 KB Output is correct
2 Correct 149 ms 22828 KB Output is correct
3 Correct 154 ms 22848 KB Output is correct
4 Correct 159 ms 22852 KB Output is correct
5 Correct 159 ms 22828 KB Output is correct
6 Correct 161 ms 31240 KB Output is correct
7 Correct 203 ms 28308 KB Output is correct
8 Correct 166 ms 26884 KB Output is correct
9 Correct 162 ms 25420 KB Output is correct
10 Incorrect 154 ms 22892 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12108 KB Output is correct
2 Correct 8 ms 12108 KB Output is correct
3 Correct 9 ms 12108 KB Output is correct
4 Correct 10 ms 12228 KB Output is correct
5 Correct 9 ms 12140 KB Output is correct
6 Correct 8 ms 12136 KB Output is correct
7 Correct 8 ms 12108 KB Output is correct
8 Correct 8 ms 12108 KB Output is correct
9 Correct 7 ms 12108 KB Output is correct
10 Correct 7 ms 12064 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 8 ms 12128 KB Output is correct
13 Correct 8 ms 12108 KB Output is correct
14 Correct 8 ms 12108 KB Output is correct
15 Correct 8 ms 12196 KB Output is correct
16 Incorrect 8 ms 12108 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 22812 KB Output is correct
2 Correct 159 ms 22812 KB Output is correct
3 Correct 163 ms 22408 KB Output is correct
4 Correct 170 ms 21824 KB Output is correct
5 Correct 164 ms 21104 KB Output is correct
6 Correct 145 ms 20728 KB Output is correct
7 Correct 140 ms 20676 KB Output is correct
8 Correct 171 ms 20552 KB Output is correct
9 Correct 130 ms 20396 KB Output is correct
10 Correct 133 ms 20348 KB Output is correct
11 Correct 127 ms 20300 KB Output is correct
12 Correct 125 ms 20328 KB Output is correct
13 Correct 128 ms 20292 KB Output is correct
14 Correct 128 ms 22028 KB Output is correct
15 Correct 192 ms 28228 KB Output is correct
16 Correct 168 ms 26308 KB Output is correct
17 Correct 168 ms 26944 KB Output is correct
18 Correct 187 ms 25348 KB Output is correct
19 Incorrect 158 ms 21812 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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