oj.uz

Submission #252413

# Submission time Handle Problem Language Result Execution time Memory
252413 2020-07-25T13:43:09 Z shayan_p Duathlon (APIO18_duathlon) C++14
0 / 100
 137 ms 34468 KB 
// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<int> v[maxn], g[maxn], vec;
int up[maxn], h[maxn], val[maxn], n;
bool mark[maxn];
int C;

void add_edge(int a, int b){
    g[a].PB(b);
    g[b].PB(a);
}
void prep(int u){
    n++;
    mark[u] = 1;
    up[u] = h[u];
    for(int y : v[u]){
	if(!mark[y]){
	    int SZ = sz(vec);
	    
	    h[y] = h[u] + 1;
	    prep(y);
	    up[u] = min(up[u], up[y]);
	    
	    if(up[y] == h[u]){
		while(sz(vec) > SZ){
		    add_edge(vec.back(), C);
		    vec.pop_back();
		}
		add_edge(u, C);
		val[C] = sz(g[C]) - 1;
		C++;
	    }
	}
	else{
	    up[u] = min(up[u], h[y]);	    
	}	    
    }    
    vec.PB(u);
}

ll ans;
int SZ[maxn];

void dfs(int u, int par = -1){
    SZ[u] = (u < n);
    ll num = 0;
    for(int y : g[u])
	if(y != par)
	    dfs(y, u), SZ[u]+= SZ[y], num+= 1ll * SZ[y] * (SZ[y]-1);
    num+= 1ll * (n-SZ[u]) * (n-SZ[u]-1);
    ans+= 1ll * val[u] * (1ll * n * (n-1) - num);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int N, m;
    cin >> N >> m;
    for(int i = 0; i < m; i++){
	int a, b;
	cin >> a >> b;
	--a, --b;
	v[a].PB(b);
	v[b].PB(a);
    }
    C = N;
    for(int i = 0; i < N; i++){
	if(!mark[i]){
	    n = 0;
	    prep(i);
	    ans = -1ll * n * (n-1);
	    dfs(i);
	}
    }
    return cout << ans << endl, 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 32152 KB Output is correct
2 Correct 106 ms 32116 KB Output is correct
3 Incorrect 115 ms 30836 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 26104 KB Output is correct
2 Correct 105 ms 26104 KB Output is correct
3 Correct 100 ms 26104 KB Output is correct
4 Correct 103 ms 26104 KB Output is correct
5 Correct 103 ms 26104 KB Output is correct
6 Correct 111 ms 34468 KB Output is correct
7 Correct 117 ms 31608 KB Output is correct
8 Correct 110 ms 30200 KB Output is correct
9 Correct 110 ms 28792 KB Output is correct
10 Incorrect 118 ms 26232 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 26104 KB Output is correct
2 Correct 108 ms 25976 KB Output is correct
3 Correct 110 ms 25336 KB Output is correct
4 Correct 106 ms 24444 KB Output is correct
5 Correct 98 ms 23672 KB Output is correct
6 Correct 98 ms 23288 KB Output is correct
7 Correct 95 ms 23160 KB Output is correct
8 Correct 106 ms 23032 KB Output is correct
9 Correct 93 ms 22852 KB Output is correct
10 Correct 89 ms 22776 KB Output is correct
11 Correct 85 ms 22904 KB Output is correct
12 Correct 82 ms 22904 KB Output is correct
13 Correct 103 ms 23048 KB Output is correct
14 Correct 81 ms 25080 KB Output is correct
15 Correct 137 ms 31224 KB Output is correct
16 Correct 135 ms 29304 KB Output is correct
17 Correct 126 ms 29792 KB Output is correct
18 Correct 115 ms 28024 KB Output is correct
19 Incorrect 108 ms 24432 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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