oj.uz

Submission #368927

# Submission time Handle Problem Language Result Execution time Memory
368927 2021-02-20T08:12:04 Z YJU Duathlon (APIO18_duathlon) C++14
31 / 100
 229 ms 71916 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e6+5;
const ld pi=acos(-1);
const ll INF=(1LL<<60);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,m,x,y;
ll low[N],depth[N],cnt=0,ptr,w[N],ans,sz[N];
vector<ll> G[N],v[N];

ll stk[N],now;

void DFS1(ll nd,ll pa){
	++cnt;
	low[nd]=depth[nd]=depth[pa]+1;
	stk[++now]=nd;
	for(ll i:v[nd]){
		if(i==pa)continue;
		if(depth[i]){
			low[nd]=min(low[nd],depth[i]);
		}else{
			//
			//
			DFS1(i,nd);
			if(low[i]>=depth[nd]){
				//cout<<"FIND BCC\n";
				++ptr;
				while(stk[now]!=nd){
					//cout<<stk[now]<<" ";
					++w[ptr];w[stk[now]]=-1;
					G[stk[now]].pb(ptr);
					G[ptr].pb(stk[now]);
					--now;
				}
				//cout<<stk[now]<<"\n";
				++w[ptr];w[stk[now]]=-1;
				G[stk[now]].pb(ptr);
				G[ptr].pb(stk[now]);
			}
			low[nd]=min(low[nd],low[i]);
		}
	}
}

void DFS2(ll nd,ll pa){
	sz[nd]=(nd<=n?1:0);
	for(auto i:G[nd]){
		if(i==pa)continue;
		DFS2(i,nd);
		ans+=2*w[nd]*sz[nd]*sz[i];
		sz[nd]+=sz[i];
	}
	ans+=2*w[nd]*sz[nd]*(cnt-sz[nd]);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	ptr=n;
	REP(i,m){
		cin>>x>>y;
		v[x].pb(y),v[y].pb(x);
	}
	REP1(i,n){
		if(!depth[i]){
			cnt=now=0;
			DFS1(i,0);
			DFS2(i,0);
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47340 KB Output is correct
2 Correct 32 ms 47340 KB Output is correct
3 Correct 32 ms 47340 KB Output is correct
4 Correct 35 ms 47340 KB Output is correct
5 Correct 34 ms 47340 KB Output is correct
6 Correct 32 ms 47368 KB Output is correct
7 Incorrect 35 ms 47468 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47340 KB Output is correct
2 Correct 32 ms 47340 KB Output is correct
3 Correct 32 ms 47340 KB Output is correct
4 Correct 35 ms 47340 KB Output is correct
5 Correct 34 ms 47340 KB Output is correct
6 Correct 32 ms 47368 KB Output is correct
7 Incorrect 35 ms 47468 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 67424 KB Output is correct
2 Correct 136 ms 67424 KB Output is correct
3 Correct 173 ms 67556 KB Output is correct
4 Correct 167 ms 66540 KB Output is correct
5 Correct 199 ms 64516 KB Output is correct
6 Correct 171 ms 66404 KB Output is correct
7 Correct 181 ms 64360 KB Output is correct
8 Correct 188 ms 64992 KB Output is correct
9 Correct 149 ms 62828 KB Output is correct
10 Correct 186 ms 63080 KB Output is correct
11 Correct 130 ms 60396 KB Output is correct
12 Correct 175 ms 60064 KB Output is correct
13 Correct 152 ms 59884 KB Output is correct
14 Correct 124 ms 59628 KB Output is correct
15 Correct 125 ms 58348 KB Output is correct
16 Correct 98 ms 58092 KB Output is correct
17 Correct 36 ms 50412 KB Output is correct
18 Correct 39 ms 50464 KB Output is correct
19 Correct 41 ms 50284 KB Output is correct
20 Correct 35 ms 50284 KB Output is correct
21 Correct 37 ms 50284 KB Output is correct
22 Correct 37 ms 50284 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47532 KB Output is correct
2 Correct 32 ms 47468 KB Output is correct
3 Correct 33 ms 47468 KB Output is correct
4 Correct 37 ms 47596 KB Output is correct
5 Correct 37 ms 47596 KB Output is correct
6 Correct 32 ms 47596 KB Output is correct
7 Correct 33 ms 47596 KB Output is correct
8 Correct 31 ms 47596 KB Output is correct
9 Correct 32 ms 47596 KB Output is correct
10 Correct 32 ms 47468 KB Output is correct
11 Correct 33 ms 47596 KB Output is correct
12 Correct 36 ms 47468 KB Output is correct
13 Correct 37 ms 47468 KB Output is correct
14 Correct 35 ms 47468 KB Output is correct
15 Correct 32 ms 47468 KB Output is correct
16 Correct 36 ms 47468 KB Output is correct
17 Correct 31 ms 47468 KB Output is correct
18 Correct 32 ms 47468 KB Output is correct
19 Correct 33 ms 47616 KB Output is correct
20 Correct 32 ms 47468 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 63980 KB Output is correct
2 Correct 191 ms 63912 KB Output is correct
3 Correct 205 ms 64128 KB Output is correct
4 Correct 179 ms 63980 KB Output is correct
5 Correct 162 ms 63980 KB Output is correct
6 Correct 206 ms 71916 KB Output is correct
7 Correct 213 ms 69484 KB Output is correct
8 Correct 218 ms 67948 KB Output is correct
9 Correct 208 ms 66540 KB Output is correct
10 Correct 166 ms 63980 KB Output is correct
11 Correct 155 ms 63980 KB Output is correct
12 Correct 170 ms 64128 KB Output is correct
13 Correct 176 ms 63952 KB Output is correct
14 Correct 154 ms 63008 KB Output is correct
15 Correct 129 ms 61932 KB Output is correct
16 Correct 98 ms 58364 KB Output is correct
17 Correct 126 ms 64224 KB Output is correct
18 Correct 137 ms 64300 KB Output is correct
19 Correct 169 ms 64596 KB Output is correct
20 Correct 173 ms 64428 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47468 KB Output is correct
2 Correct 39 ms 47596 KB Output is correct
3 Incorrect 32 ms 47468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 63908 KB Output is correct
2 Correct 153 ms 63724 KB Output is correct
3 Incorrect 182 ms 63484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47340 KB Output is correct
2 Correct 32 ms 47340 KB Output is correct
3 Correct 32 ms 47340 KB Output is correct
4 Correct 35 ms 47340 KB Output is correct
5 Correct 34 ms 47340 KB Output is correct
6 Correct 32 ms 47368 KB Output is correct
7 Incorrect 35 ms 47468 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 47340 KB Output is correct
2 Correct 32 ms 47340 KB Output is correct
3 Correct 32 ms 47340 KB Output is correct
4 Correct 35 ms 47340 KB Output is correct
5 Correct 34 ms 47340 KB Output is correct
6 Correct 32 ms 47368 KB Output is correct
7 Incorrect 35 ms 47468 KB Output isn't correct
8 Halted 0 ms 0 KB -