oj.uz

Submission #62280

# Submission time Handle Problem Language Result Execution time Memory
62280 2018-07-28T01:45:52 Z Benq Duathlon (APIO18_duathlon) C++11
66 / 100
 451 ms 93000 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

DSU<MX> D;

template<int SZ> struct BCC {
    int N, ti = 0;
    vi adj[SZ];
    int disc[SZ], low[SZ], comp[SZ], par[SZ];
    vector<vpi> fin;
    vpi st;
    vi bad[SZ];
    
    void addEdge(int u, int v) {
        adj[u].pb(v), adj[v].pb(u);
    }
    
    void BCCutil(int u, bool root = 0) {
        disc[u] = low[u] = ti++;
        int child = 0;
        
        for (int i: adj[u]) if (i != par[u]) {
            if (disc[i] == -1) {
                child ++; par[i] = u; 
                BCCutil(i);
                low[u] = min(low[u],low[i]);
                
                if (disc[u] < low[i]) { // bridge
                    bad[u].pb(i), bad[i].pb(u);
                } else D.unite(i,u);
            } else if (disc[i] < disc[u]) {
                low[u] = min(low[u],disc[i]);
            }
        }
    }
    
    void bcc() {
        FOR(i,1,N+1) par[i] = disc[i] = low[i] = -1;
        FOR(i,1,N+1) if (disc[i] == -1) {
            BCCutil(i,1);
            if (sz(st)) fin.pb(st);
            st.clear();
        }
    }
};

int n,m,sz[MX], totsz[MX];
ll ans = 0;
set<pi> adj[MX];
BCC<MX> B;
bool visit[MX];

void dfs1(int x, int y = 0) {
    visit[x] = 1;
    totsz[x] = sz[x];
    for (auto i: adj[x]) if (i.f != x && i.f != y) {
        dfs1(i.f,x);
        totsz[x] += totsz[i.f];
    }
}

void dfs2(int x, int p, int y = 0) {
    ans += (ll)sz[x]*(totsz[p]-1)*(totsz[p]-2);
    
    map<int,vi> m;
    for (auto i: adj[x]) if (i.f != x) {
        ll tmp = 0;
        if (totsz[i.f] > totsz[x]) tmp = totsz[p]-totsz[x];
        else tmp = totsz[i.f];
        m[i.s].pb(tmp);
    }
    for (auto a: m) {
        // for vertex: all separate
        ll tot = 1;
        for (auto x: a.s) {
            ans -= (ll)x*(x-1);
            tot += x;
        }
        ans -= (ll)(sz[x]-1)*tot*(tot-1);
    }
    
    for (auto i: adj[x]) if (i.f != x && i.f != y) {
        dfs2(i.f,p,x);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    F0R(i,m) {
        int a,b; cin >> a >> b;
        B.addEdge(a,b);
    }
    B.N = n;
    B.bcc();
    
    FOR(i,1,n+1) {
        sz[D.get(i)] ++;
        for (int j: B.adj[i]) if (D.get(i) != D.get(j)) {
            adj[D.get(i)].insert({D.get(j),i});
        }
    }
    FOR(i,1,n+1) if (!visit[i]) {
        dfs1(i);
        dfs2(i,i);
    }
    cout << ans;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10488 KB Output is correct
2 Correct 11 ms 10600 KB Output is correct
3 Correct 12 ms 10680 KB Output is correct
4 Correct 12 ms 10760 KB Output is correct
5 Correct 12 ms 10800 KB Output is correct
6 Correct 11 ms 10800 KB Output is correct
7 Correct 12 ms 10800 KB Output is correct
8 Incorrect 14 ms 10904 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10488 KB Output is correct
2 Correct 11 ms 10600 KB Output is correct
3 Correct 12 ms 10680 KB Output is correct
4 Correct 12 ms 10760 KB Output is correct
5 Correct 12 ms 10800 KB Output is correct
6 Correct 11 ms 10800 KB Output is correct
7 Correct 12 ms 10800 KB Output is correct
8 Incorrect 14 ms 10904 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 24728 KB Output is correct
2 Correct 179 ms 25912 KB Output is correct
3 Correct 307 ms 37652 KB Output is correct
4 Correct 201 ms 37652 KB Output is correct
5 Correct 229 ms 37652 KB Output is correct
6 Correct 252 ms 39796 KB Output is correct
7 Correct 240 ms 39796 KB Output is correct
8 Correct 310 ms 39808 KB Output is correct
9 Correct 286 ms 39808 KB Output is correct
10 Correct 208 ms 39808 KB Output is correct
11 Correct 187 ms 39808 KB Output is correct
12 Correct 157 ms 39808 KB Output is correct
13 Correct 169 ms 39808 KB Output is correct
14 Correct 131 ms 39808 KB Output is correct
15 Correct 132 ms 39808 KB Output is correct
16 Correct 139 ms 39808 KB Output is correct
17 Correct 23 ms 39808 KB Output is correct
18 Correct 16 ms 39808 KB Output is correct
19 Correct 18 ms 39808 KB Output is correct
20 Correct 17 ms 39808 KB Output is correct
21 Correct 21 ms 39808 KB Output is correct
22 Correct 17 ms 39808 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 39808 KB Output is correct
2 Correct 17 ms 39808 KB Output is correct
3 Correct 15 ms 39808 KB Output is correct
4 Correct 14 ms 39808 KB Output is correct
5 Correct 18 ms 39808 KB Output is correct
6 Correct 15 ms 39808 KB Output is correct
7 Correct 17 ms 39808 KB Output is correct
8 Correct 16 ms 39808 KB Output is correct
9 Correct 16 ms 39808 KB Output is correct
10 Correct 52 ms 39808 KB Output is correct
11 Correct 12 ms 39808 KB Output is correct
12 Correct 14 ms 39808 KB Output is correct
13 Correct 15 ms 39808 KB Output is correct
14 Correct 15 ms 39808 KB Output is correct
15 Correct 16 ms 39808 KB Output is correct
16 Correct 15 ms 39808 KB Output is correct
17 Correct 16 ms 39808 KB Output is correct
18 Correct 13 ms 39808 KB Output is correct
19 Correct 14 ms 39808 KB Output is correct
20 Correct 15 ms 39808 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 48212 KB Output is correct
2 Correct 329 ms 49492 KB Output is correct
3 Correct 391 ms 50676 KB Output is correct
4 Correct 346 ms 51884 KB Output is correct
5 Correct 347 ms 53112 KB Output is correct
6 Correct 451 ms 69524 KB Output is correct
7 Correct 364 ms 69524 KB Output is correct
8 Correct 367 ms 69524 KB Output is correct
9 Correct 306 ms 69524 KB Output is correct
10 Correct 267 ms 69524 KB Output is correct
11 Correct 292 ms 69524 KB Output is correct
12 Correct 330 ms 69524 KB Output is correct
13 Correct 282 ms 69524 KB Output is correct
14 Correct 219 ms 69524 KB Output is correct
15 Correct 204 ms 69524 KB Output is correct
16 Correct 154 ms 69524 KB Output is correct
17 Correct 321 ms 69524 KB Output is correct
18 Correct 292 ms 69568 KB Output is correct
19 Correct 284 ms 70880 KB Output is correct
20 Correct 233 ms 71868 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 71868 KB Output is correct
2 Correct 15 ms 71868 KB Output is correct
3 Correct 17 ms 71868 KB Output is correct
4 Correct 16 ms 71868 KB Output is correct
5 Correct 12 ms 71868 KB Output is correct
6 Correct 16 ms 71868 KB Output is correct
7 Correct 13 ms 71868 KB Output is correct
8 Correct 12 ms 71868 KB Output is correct
9 Correct 12 ms 71868 KB Output is correct
10 Correct 16 ms 71868 KB Output is correct
11 Correct 14 ms 71868 KB Output is correct
12 Correct 14 ms 71868 KB Output is correct
13 Correct 16 ms 71868 KB Output is correct
14 Correct 16 ms 71868 KB Output is correct
15 Correct 12 ms 71868 KB Output is correct
16 Correct 13 ms 71868 KB Output is correct
17 Correct 13 ms 71868 KB Output is correct
18 Correct 13 ms 71868 KB Output is correct
19 Correct 12 ms 71868 KB Output is correct
20 Correct 15 ms 71868 KB Output is correct
21 Correct 14 ms 71868 KB Output is correct
22 Correct 14 ms 71868 KB Output is correct
23 Correct 14 ms 71868 KB Output is correct
24 Correct 14 ms 71868 KB Output is correct
25 Correct 14 ms 71868 KB Output is correct
26 Correct 14 ms 71868 KB Output is correct
27 Correct 14 ms 71868 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 72544 KB Output is correct
2 Correct 273 ms 73692 KB Output is correct
3 Correct 266 ms 73692 KB Output is correct
4 Correct 265 ms 73692 KB Output is correct
5 Correct 205 ms 73692 KB Output is correct
6 Correct 187 ms 73692 KB Output is correct
7 Correct 194 ms 73692 KB Output is correct
8 Correct 154 ms 73692 KB Output is correct
9 Correct 150 ms 73692 KB Output is correct
10 Correct 152 ms 73692 KB Output is correct
11 Correct 148 ms 73724 KB Output is correct
12 Correct 145 ms 75000 KB Output is correct
13 Correct 127 ms 75000 KB Output is correct
14 Correct 135 ms 76304 KB Output is correct
15 Correct 314 ms 93000 KB Output is correct
16 Correct 291 ms 93000 KB Output is correct
17 Correct 330 ms 93000 KB Output is correct
18 Correct 290 ms 93000 KB Output is correct
19 Correct 241 ms 93000 KB Output is correct
20 Correct 224 ms 93000 KB Output is correct
21 Correct 249 ms 93000 KB Output is correct
22 Correct 183 ms 93000 KB Output is correct
23 Correct 150 ms 93000 KB Output is correct
24 Correct 238 ms 93000 KB Output is correct
25 Correct 239 ms 93000 KB Output is correct
26 Correct 254 ms 93000 KB Output is correct
27 Correct 224 ms 93000 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10488 KB Output is correct
2 Correct 11 ms 10600 KB Output is correct
3 Correct 12 ms 10680 KB Output is correct
4 Correct 12 ms 10760 KB Output is correct
5 Correct 12 ms 10800 KB Output is correct
6 Correct 11 ms 10800 KB Output is correct
7 Correct 12 ms 10800 KB Output is correct
8 Incorrect 14 ms 10904 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10488 KB Output is correct
2 Correct 11 ms 10600 KB Output is correct
3 Correct 12 ms 10680 KB Output is correct
4 Correct 12 ms 10760 KB Output is correct
5 Correct 12 ms 10800 KB Output is correct
6 Correct 11 ms 10800 KB Output is correct
7 Correct 12 ms 10800 KB Output is correct
8 Incorrect 14 ms 10904 KB Output isn't correct
9 Halted 0 ms 0 KB -