oj.uz

Submission #370706

# Submission time Handle Problem Language Result Execution time Memory
370706 2021-02-24T13:46:25 Z Leonardo_Paes Duathlon (APIO18_duathlon) C++17
31 / 100
 234 ms 26776 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ar array
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),(a).end()
typedef pair<int,int> pii;
#define f first
#define s second
const int maxn = 1e5+10;
vector<int> grafo[maxn], aux[maxn];
int n, m, dp[maxn], sz[maxn], qtd[maxn], qtd2[maxn], color[maxn], c;
bool instack[maxn], mark[maxn];
stack<int> s;
void compress(int u, int p = 0){
    instack[u] = mark[u] = 1;
    s.push(u);
    //cout << "entrei em " << u << endl;
    for(int v : grafo[u]){
        if(instack[v] and v != p){
            c++;
            int vv;
            do{
                vv = s.top();
                //cout << vv << endl;
                color[vv] = c;
                instack[vv] = 0;
                s.pop();
            }while(vv != v);
        }
        if(!mark[v]) compress(v, u);
    }
    if(instack[u]) s.pop();
    instack[u] = 0;
}
int solve(int u, int p = 0){ // lca of path is u, 1 as a root
    int ans = qtd[u]*(qtd[u]-1)*(qtd[u]-2)/2; // sum of dps
    sz[u] = qtd[u];
    for(int v : grafo[u]){
        if(v == p) continue;
        ans += solve(v, u);
        sz[u] += sz[v];
        qtd2[u] += qtd2[v] + (sz[v] * qtd[u]);
    }
    int qtdd = sz[u] - 1;
    for(int v : grafo[u]){
        if(v == p) continue;
        qtdd -= sz[v];
        dp[u] += sz[v] * qtdd * qtd[u];
        dp[u] += (sz[u]  - sz[v]) * qtd2[v];
    }
    return ans + dp[u];
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int u, v;
        cin >> u >> v;
        grafo[u].push_back(v);
        grafo[v].push_back(u);
    }
    for(int i=1; i<=n; i++) aux[i] = grafo[i];
    for(int i=1; i<=n; i++) if(!mark[i]) compress(i);
    for(int i=1; i<=n; i++) grafo[i].clear();
    set<pair<int,int>> edges;
    for(int i=1; i<=n; i++){
        if(!color[i]) color[i] = ++c;
        qtd[color[i]]++;
    }
    for(int i=1; i<=n; i++){
        for(int e : aux[i]){
            int u = color[i], v = color[e];
            if(u > v) swap(u, v);
            if(u == v or edges.count({u, v})) continue;
            edges.insert({u, v});
            grafo[u].push_back(v);
            grafo[v].push_back(u);
        }
    }
    int ans = 0;
    for(int i=1; i<=c; i++){
        if(!sz[i]) ans += solve(i);
    }
    cout << 2*ans << "\n";
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 20972 KB Output is correct
2 Correct 108 ms 22184 KB Output is correct
3 Correct 144 ms 22124 KB Output is correct
4 Correct 110 ms 21740 KB Output is correct
5 Correct 129 ms 19436 KB Output is correct
6 Correct 144 ms 21868 KB Output is correct
7 Correct 152 ms 21100 KB Output is correct
8 Correct 158 ms 21356 KB Output is correct
9 Correct 145 ms 20204 KB Output is correct
10 Correct 136 ms 19692 KB Output is correct
11 Correct 117 ms 17644 KB Output is correct
12 Correct 123 ms 17516 KB Output is correct
13 Correct 96 ms 17516 KB Output is correct
14 Correct 95 ms 17260 KB Output is correct
15 Correct 88 ms 16876 KB Output is correct
16 Correct 92 ms 16492 KB Output is correct
17 Correct 9 ms 8556 KB Output is correct
18 Correct 11 ms 8556 KB Output is correct
19 Correct 9 ms 8428 KB Output is correct
20 Correct 9 ms 8300 KB Output is correct
21 Correct 9 ms 8172 KB Output is correct
22 Correct 9 ms 8172 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 22508 KB Output is correct
2 Correct 185 ms 22508 KB Output is correct
3 Correct 185 ms 22560 KB Output is correct
4 Correct 178 ms 22508 KB Output is correct
5 Correct 187 ms 22636 KB Output is correct
6 Correct 219 ms 26776 KB Output is correct
7 Correct 214 ms 25460 KB Output is correct
8 Correct 209 ms 24684 KB Output is correct
9 Correct 188 ms 23884 KB Output is correct
10 Correct 189 ms 22508 KB Output is correct
11 Correct 179 ms 22508 KB Output is correct
12 Correct 181 ms 22636 KB Output is correct
13 Correct 234 ms 22636 KB Output is correct
14 Correct 164 ms 21740 KB Output is correct
15 Correct 151 ms 20588 KB Output is correct
16 Correct 87 ms 17004 KB Output is correct
17 Correct 155 ms 21856 KB Output is correct
18 Correct 149 ms 21724 KB Output is correct
19 Correct 143 ms 21844 KB Output is correct
20 Correct 143 ms 21852 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 22508 KB Output is correct
2 Correct 189 ms 22380 KB Output is correct
3 Incorrect 186 ms 20076 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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