oj.uz

Submission #849648

# Submission time Handle Problem Language Result Execution time Memory
849648 2023-09-15T07:31:20 Z ntkphong Duathlon (APIO18_duathlon) C++14
66 / 100
 120 ms 25028 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int mxN = 1e5 + 10;
 
vector<int> lab;
    
void init(int n) {
    lab.resize(n + 10);
    for(int i = 1; i <= n; i ++) lab[i] = -1;
}
    
int get_root(int u) {
    return lab[u] < 0 ? u : lab[u] = get_root(lab[u]);
}
    
bool unite(int u, int v) {
    u = get_root(u);
    v = get_root(v);
        
    if(u == v) return false;
    if(lab[u] > lab[v]) swap(u, v);
        
    lab[u] += lab[v];
    lab[v] = u;
        
    return true;
}
    
int get_size(int u) {
    u = get_root(u);
    return - lab[u];
}
 
int n, m;
vector<vector<int>> adj(mxN), vertex(mxN);
int num[mxN], low[mxN], timer = 0;
 
int vis[mxN];
long long dp[mxN][2];
long long sum = 0;
 
void tanjan(int u, int par) {
    num[u] = low[u] = ++ timer;
    
    for(int v : adj[u]) {
        if(v == par) continue ;
        
        if(num[v]) {
            low[u] = min(low[u], num[v]);
        } else {
            tanjan(v, u);
            low[u] = min(low[u], low[v]);
            
            if(low[v] <= num[u]) {
                unite(u, v);                
            }
        }
    }
}
 
void dfs(int u, int par) {
    int root = get_root(u);
    vis[root] = 1;
    
    sum += get_size(root) * (get_size(root) - 1) * (get_size(root) - 2);
    //cout << 3 << " " << get_size(root) * (get_size(root) - 1) * (get_size(root) - 2) << "\n";
    dp[root][0] = get_size(root);
    dp[root][1] = (get_size(root) - 1) * (get_size(root) - 1);
    
    for(int x : vertex[root]) {
        if(x == u) continue ;
        array<long long, 2> F = {0, 0};
            
        for(int v : adj[x]) {
            if(get_root(v) == root) continue ;
            if(vis[get_root(v)]) continue ;
            if(v == par) continue ;
                
            dfs(v, x);
                
            v = get_root(v);
            sum += 2LL * F[0] * dp[v][1] + 2LL * F[1] * dp[v][0] + 2LL * F[0] * dp[v][0];
            //cout << 1 << " " << 2LL * F[0] * dp[v][1] << " " << 2LL * F[1] * dp[v][0] + 2LL * F[0] * dp[v][0] << "\n";
            F[0] += dp[v][0];
            F[1] += dp[v][1]; 
        }
            
        sum += 2LL * dp[root][0] * F[1] + 2LL * dp[root][1] * F[0]; 
        //cout <<  2 << " " << 2LL * dp[root][0] * F[1] << " " << 2LL * dp[root][1] * F[0] << "\n";
        dp[root][0] += F[0];
        dp[root][1] += F[0] * get_size(root) + F[1];
    }
    
    for(int x : vertex[root]) {
        if(x != u) continue ;
        array<long long, 2> F = {0, 0};
            
        for(int v : adj[x]) {
            if(get_root(v) == root) continue ;
            if(vis[get_root(v)]) continue ;
            if(v == par) continue ;
                
            dfs(v, x);
                
            v = get_root(v);
            sum += 2LL * F[0] * dp[v][1] + 2LL * F[1] * dp[v][0] + 2LL * F[0] * dp[v][0];
            //cout << 1 << " " << 2LL * F[0] * dp[v][1] << " " << 2LL * F[1] * dp[v][0] + 2LL * F[0] * dp[v][0] << "\n";
            F[0] += dp[v][0];
            F[1] += dp[v][1]; 
        }
            
        sum += 2LL * dp[root][0] * F[1] + 2LL * dp[root][1] * F[0]; 
        //cout <<  2 << " " << 2LL * dp[root][0] * F[1] << " " << 2LL * dp[root][1] * F[0] << "\n";
        dp[root][0] += F[0];
        dp[root][1] += F[0] + F[1];
    }
}
 
signed main() {
 
    cin.tie(0)->sync_with_stdio(0);
 
    cin >> n >> m;
    
    init(n);
    
    for(int i = 1; i <= m; i ++) {
        int u, v;
        cin >> u >> v;
        
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    for(int i = 1; i <= n; i ++) if(!num[i]) tanjan(i, i);
    
    for(int i = 1; i <= n; i ++) {
        int root = get_root(i);
        vertex[root].push_back(i);
    } 
    
    for(int i = 1; i <= n; i ++) if(!vis[get_root(i)]) dfs(i, i); 
    
    cout << sum << "\n";
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5172 KB Output is correct
2 Correct 3 ms 5172 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 5176 KB Output is correct
8 Incorrect 3 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5172 KB Output is correct
2 Correct 3 ms 5172 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 5176 KB Output is correct
8 Incorrect 3 ms 4956 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 40 ms 22468 KB Output is correct
2 Correct 42 ms 20680 KB Output is correct
3 Correct 50 ms 21964 KB Output is correct
4 Correct 45 ms 21236 KB Output is correct
5 Correct 43 ms 19372 KB Output is correct
6 Correct 53 ms 20940 KB Output is correct
7 Correct 60 ms 19148 KB Output is correct
8 Correct 67 ms 19456 KB Output is correct
9 Correct 54 ms 17748 KB Output is correct
10 Correct 59 ms 17916 KB Output is correct
11 Correct 87 ms 16316 KB Output is correct
12 Correct 62 ms 16236 KB Output is correct
13 Correct 71 ms 16212 KB Output is correct
14 Correct 51 ms 15920 KB Output is correct
15 Correct 53 ms 15968 KB Output is correct
16 Correct 39 ms 15504 KB Output is correct
17 Correct 10 ms 12892 KB Output is correct
18 Correct 10 ms 12892 KB Output is correct
19 Correct 10 ms 12892 KB Output is correct
20 Correct 14 ms 13044 KB Output is correct
21 Correct 11 ms 13144 KB Output is correct
22 Correct 11 ms 12892 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 17920 KB Output is correct
2 Correct 95 ms 17968 KB Output is correct
3 Correct 80 ms 17800 KB Output is correct
4 Correct 61 ms 17960 KB Output is correct
5 Correct 89 ms 17796 KB Output is correct
6 Correct 95 ms 25028 KB Output is correct
7 Correct 95 ms 22968 KB Output is correct
8 Correct 80 ms 21480 KB Output is correct
9 Correct 67 ms 20200 KB Output is correct
10 Correct 87 ms 17960 KB Output is correct
11 Correct 80 ms 17868 KB Output is correct
12 Correct 78 ms 18176 KB Output is correct
13 Correct 55 ms 17748 KB Output is correct
14 Correct 45 ms 17488 KB Output is correct
15 Correct 61 ms 17044 KB Output is correct
16 Correct 41 ms 15956 KB Output is correct
17 Correct 46 ms 18160 KB Output is correct
18 Correct 55 ms 18156 KB Output is correct
19 Correct 54 ms 18108 KB Output is correct
20 Correct 49 ms 18156 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 17820 KB Output is correct
2 Correct 55 ms 17756 KB Output is correct
3 Correct 54 ms 17476 KB Output is correct
4 Correct 66 ms 17004 KB Output is correct
5 Correct 74 ms 16496 KB Output is correct
6 Correct 58 ms 15952 KB Output is correct
7 Correct 66 ms 16140 KB Output is correct
8 Correct 63 ms 15676 KB Output is correct
9 Correct 41 ms 15952 KB Output is correct
10 Correct 65 ms 15680 KB Output is correct
11 Correct 47 ms 15568 KB Output is correct
12 Correct 44 ms 14960 KB Output is correct
13 Correct 37 ms 14392 KB Output is correct
14 Correct 43 ms 15248 KB Output is correct
15 Correct 120 ms 21828 KB Output is correct
16 Correct 85 ms 20436 KB Output is correct
17 Correct 104 ms 20268 KB Output is correct
18 Correct 81 ms 19120 KB Output is correct
19 Correct 71 ms 16972 KB Output is correct
20 Correct 66 ms 16980 KB Output is correct
21 Correct 62 ms 16980 KB Output is correct
22 Correct 59 ms 16500 KB Output is correct
23 Correct 83 ms 16104 KB Output is correct
24 Correct 51 ms 17236 KB Output is correct
25 Correct 109 ms 17316 KB Output is correct
26 Correct 90 ms 17024 KB Output is correct
27 Correct 87 ms 16772 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5172 KB Output is correct
2 Correct 3 ms 5172 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 5176 KB Output is correct
8 Incorrect 3 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5172 KB Output is correct
2 Correct 3 ms 5172 KB Output is correct
3 Correct 2 ms 4952 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 3 ms 5176 KB Output is correct
8 Incorrect 3 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -