oj.uz

Submission #370757

# Submission time Handle Problem Language Result Execution time Memory
370757 2021-02-24T14:36:15 Z Leonardo_Paes Duathlon (APIO18_duathlon) C++17
31 / 100
 275 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); // 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] - 1 + 3 * (qtd[u] - 1) * (qtd[u] - 2));
        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 5 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 5 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 104 ms 20968 KB Output is correct
2 Correct 89 ms 20972 KB Output is correct
3 Correct 144 ms 20972 KB Output is correct
4 Correct 104 ms 20508 KB Output is correct
5 Correct 109 ms 18156 KB Output is correct
6 Correct 136 ms 20588 KB Output is correct
7 Correct 160 ms 19692 KB Output is correct
8 Correct 154 ms 20076 KB Output is correct
9 Correct 154 ms 18924 KB Output is correct
10 Correct 140 ms 18540 KB Output is correct
11 Correct 104 ms 16492 KB Output is correct
12 Correct 112 ms 16480 KB Output is correct
13 Correct 102 ms 16492 KB Output is correct
14 Correct 94 ms 16364 KB Output is correct
15 Correct 89 ms 16108 KB Output is correct
16 Correct 77 ms 15852 KB Output is correct
17 Correct 9 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 10 ms 8428 KB Output is correct
22 Correct 11 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 5 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 4 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 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 5 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 5 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 193 ms 22476 KB Output is correct
2 Correct 189 ms 22508 KB Output is correct
3 Correct 183 ms 22764 KB Output is correct
4 Correct 186 ms 22508 KB Output is correct
5 Correct 187 ms 22636 KB Output is correct
6 Correct 275 ms 26776 KB Output is correct
7 Correct 198 ms 25452 KB Output is correct
8 Correct 197 ms 24684 KB Output is correct
9 Correct 227 ms 23916 KB Output is correct
10 Correct 212 ms 22568 KB Output is correct
11 Correct 189 ms 22508 KB Output is correct
12 Correct 190 ms 22636 KB Output is correct
13 Correct 201 ms 22508 KB Output is correct
14 Correct 213 ms 21740 KB Output is correct
15 Correct 139 ms 20716 KB Output is correct
16 Correct 85 ms 17004 KB Output is correct
17 Correct 157 ms 22624 KB Output is correct
18 Correct 144 ms 22492 KB Output is correct
19 Correct 157 ms 22484 KB Output is correct
20 Correct 156 ms 22492 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 194 ms 22520 KB Output is correct
2 Correct 228 ms 22480 KB Output is correct
3 Incorrect 212 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 5 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 5 ms 5100 KB Output isn't correct
2 Halted 0 ms 0 KB -