oj.uz

Submission #370752

# Submission time Handle Problem Language Result Execution time Memory
370752 2021-02-24T14:30:08 Z Leonardo_Paes Duathlon (APIO18_duathlon) C++17
31 / 100
 227 ms 26904 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); // 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];
    }
    for(int v : grafo[u]){
        if(v == p) continue;
        dp[u] += sz[v] * (sz[u] - qtd[u] - sz[v]) * qtd[u]; // 1 from each
        dp[u] += sz[v] * (qtd[u] * (qtd[u] - 1));
        dp[u] += 2 * (sz[u] - sz[v]) * qtd2[v];
    }
    if(grafo[u].size() == 1){
        qtd2[u] = sz[u] - 1 + 2 * (sz[u] - 1) * (sz[u] - 2);
    }
    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);
    }
    for(int i=1; i<=n; i++){
        //cout << color[i] << " " << qtd2[color[i]] << endl;
    }
    cout << ans << "\n";
    /*
6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 4

8 9
1 2
2 3
3 4
4 2
1 5
5 6
6 7
7 8
8 5
    */
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5108 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 5108 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 96 ms 20972 KB Output is correct
2 Correct 94 ms 20972 KB Output is correct
3 Correct 139 ms 20972 KB Output is correct
4 Correct 116 ms 20588 KB Output is correct
5 Correct 114 ms 18204 KB Output is correct
6 Correct 149 ms 20740 KB Output is correct
7 Correct 148 ms 19692 KB Output is correct
8 Correct 149 ms 20460 KB Output is correct
9 Correct 151 ms 18924 KB Output is correct
10 Correct 131 ms 18540 KB Output is correct
11 Correct 103 ms 16620 KB Output is correct
12 Correct 110 ms 16748 KB Output is correct
13 Correct 96 ms 16492 KB Output is correct
14 Correct 101 ms 16364 KB Output is correct
15 Correct 80 ms 16108 KB Output is correct
16 Correct 86 ms 15724 KB Output is correct
17 Correct 11 ms 8684 KB Output is correct
18 Correct 9 ms 8812 KB Output is correct
19 Correct 9 ms 8684 KB Output is correct
20 Correct 9 ms 8556 KB Output is correct
21 Correct 8 ms 8428 KB Output is correct
22 Correct 9 ms 8428 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5228 KB Output is correct
2 Correct 5 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 5 ms 5248 KB Output is correct
7 Correct 4 ms 5228 KB Output is correct
8 Correct 5 ms 5228 KB Output is correct
9 Correct 4 ms 5228 KB Output is correct
10 Correct 4 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 5 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 4 ms 5228 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 22508 KB Output is correct
2 Correct 188 ms 22552 KB Output is correct
3 Correct 180 ms 22508 KB Output is correct
4 Correct 201 ms 22636 KB Output is correct
5 Correct 176 ms 22508 KB Output is correct
6 Correct 227 ms 26904 KB Output is correct
7 Correct 205 ms 25580 KB Output is correct
8 Correct 204 ms 24840 KB Output is correct
9 Correct 201 ms 23916 KB Output is correct
10 Correct 188 ms 22508 KB Output is correct
11 Correct 181 ms 22508 KB Output is correct
12 Correct 183 ms 22508 KB Output is correct
13 Correct 186 ms 22764 KB Output is correct
14 Correct 178 ms 21740 KB Output is correct
15 Correct 148 ms 20588 KB Output is correct
16 Correct 92 ms 17004 KB Output is correct
17 Correct 151 ms 22544 KB Output is correct
18 Correct 150 ms 22492 KB Output is correct
19 Correct 150 ms 22464 KB Output is correct
20 Correct 143 ms 22492 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 5 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 194 ms 22508 KB Output is correct
2 Correct 188 ms 22380 KB Output is correct
3 Incorrect 182 ms 19948 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 5108 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 5108 KB Output isn't correct
2 Halted 0 ms 0 KB -