oj.uz

Submission #368957

# Submission time Handle Problem Language Result Execution time Memory
368957 2021-02-20T08:19:11 Z YJU Duathlon (APIO18_duathlon) C++14
31 / 100
 245 ms 70332 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 32 ms 47340 KB Output is correct
2 Correct 31 ms 47340 KB Output is correct
3 Correct 34 ms 47468 KB Output is correct
4 Correct 31 ms 47488 KB Output is correct
5 Correct 30 ms 47340 KB Output is correct
6 Correct 30 ms 47340 KB Output is correct
7 Incorrect 36 ms 47340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47340 KB Output is correct
2 Correct 31 ms 47340 KB Output is correct
3 Correct 34 ms 47468 KB Output is correct
4 Correct 31 ms 47488 KB Output is correct
5 Correct 30 ms 47340 KB Output is correct
6 Correct 30 ms 47340 KB Output is correct
7 Incorrect 36 ms 47340 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 150 ms 66140 KB Output is correct
2 Correct 181 ms 66144 KB Output is correct
3 Correct 193 ms 66404 KB Output is correct
4 Correct 190 ms 65056 KB Output is correct
5 Correct 165 ms 63204 KB Output is correct
6 Correct 183 ms 65124 KB Output is correct
7 Correct 145 ms 63080 KB Output is correct
8 Correct 189 ms 63592 KB Output is correct
9 Correct 159 ms 61548 KB Output is correct
10 Correct 169 ms 61824 KB Output is correct
11 Correct 157 ms 59392 KB Output is correct
12 Correct 181 ms 59100 KB Output is correct
13 Correct 175 ms 58988 KB Output is correct
14 Correct 140 ms 58604 KB Output is correct
15 Correct 114 ms 57580 KB Output is correct
16 Correct 106 ms 57324 KB Output is correct
17 Correct 36 ms 50412 KB Output is correct
18 Correct 42 ms 50540 KB Output is correct
19 Correct 35 ms 50284 KB Output is correct
20 Correct 39 ms 50432 KB Output is correct
21 Correct 37 ms 50284 KB Output is correct
22 Correct 35 ms 50156 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 62652 KB Output is correct
2 Correct 165 ms 62608 KB Output is correct
3 Correct 173 ms 62700 KB Output is correct
4 Correct 153 ms 62828 KB Output is correct
5 Correct 154 ms 62700 KB Output is correct
6 Correct 202 ms 70332 KB Output is correct
7 Correct 245 ms 68204 KB Output is correct
8 Correct 210 ms 66704 KB Output is correct
9 Correct 227 ms 65260 KB Output is correct
10 Correct 176 ms 62700 KB Output is correct
11 Correct 197 ms 62700 KB Output is correct
12 Correct 151 ms 62616 KB Output is correct
13 Correct 151 ms 62600 KB Output is correct
14 Correct 173 ms 61776 KB Output is correct
15 Correct 163 ms 60780 KB Output is correct
16 Correct 127 ms 57808 KB Output is correct
17 Correct 127 ms 62944 KB Output is correct
18 Correct 129 ms 63052 KB Output is correct
19 Correct 142 ms 63316 KB Output is correct
20 Correct 138 ms 63068 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47468 KB Output is correct
2 Correct 38 ms 47468 KB Output is correct
3 Incorrect 33 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 163 ms 62700 KB Output is correct
2 Correct 178 ms 62444 KB Output is correct
3 Incorrect 155 ms 62188 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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