oj.uz

Submission #370840

# Submission time Handle Problem Language Result Execution time Memory
370840 2021-02-24T18:14:40 Z Leonardo_Paes Duathlon (APIO18_duathlon) C++17
31 / 100
 210 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] += 2 * sz[v] * (qtd[u] - 1 + (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 + (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]){
        assert(s.empty());
        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

72

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 3 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 3 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 78 ms 20972 KB Output is correct
2 Correct 107 ms 20972 KB Output is correct
3 Correct 145 ms 20972 KB Output is correct
4 Correct 90 ms 20588 KB Output is correct
5 Correct 100 ms 18028 KB Output is correct
6 Correct 121 ms 20588 KB Output is correct
7 Correct 123 ms 19692 KB Output is correct
8 Correct 145 ms 20204 KB Output is correct
9 Correct 142 ms 19052 KB Output is correct
10 Correct 127 ms 18540 KB Output is correct
11 Correct 89 ms 16492 KB Output is correct
12 Correct 101 ms 16492 KB Output is correct
13 Correct 98 ms 16492 KB Output is correct
14 Correct 94 ms 16364 KB Output is correct
15 Correct 85 ms 16236 KB Output is correct
16 Correct 81 ms 15724 KB Output is correct
17 Correct 8 ms 8684 KB Output is correct
18 Correct 8 ms 8812 KB Output is correct
19 Correct 8 ms 8684 KB Output is correct
20 Correct 8 ms 8556 KB Output is correct
21 Correct 8 ms 8556 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 4 ms 5228 KB Output is correct
2 Correct 5 ms 5228 KB Output is correct
3 Correct 5 ms 5228 KB Output is correct
4 Correct 4 ms 5356 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 5 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 4 ms 5228 KB Output is correct
10 Correct 4 ms 5228 KB Output is correct
11 Correct 4 ms 5228 KB Output is correct
12 Correct 4 ms 5228 KB Output is correct
13 Correct 4 ms 5248 KB Output is correct
14 Correct 4 ms 5228 KB Output is correct
15 Correct 5 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 178 ms 22496 KB Output is correct
2 Correct 165 ms 22512 KB Output is correct
3 Correct 165 ms 22584 KB Output is correct
4 Correct 196 ms 22508 KB Output is correct
5 Correct 173 ms 22508 KB Output is correct
6 Correct 202 ms 26904 KB Output is correct
7 Correct 183 ms 25452 KB Output is correct
8 Correct 200 ms 24684 KB Output is correct
9 Correct 210 ms 23916 KB Output is correct
10 Correct 171 ms 22508 KB Output is correct
11 Correct 176 ms 22508 KB Output is correct
12 Correct 165 ms 22508 KB Output is correct
13 Correct 176 ms 22636 KB Output is correct
14 Correct 152 ms 21612 KB Output is correct
15 Correct 140 ms 20472 KB Output is correct
16 Correct 84 ms 17004 KB Output is correct
17 Correct 156 ms 22500 KB Output is correct
18 Correct 145 ms 22492 KB Output is correct
19 Correct 144 ms 22484 KB Output is correct
20 Correct 150 ms 22460 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 169 ms 22636 KB Output is correct
2 Correct 192 ms 22380 KB Output is correct
3 Incorrect 160 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 3 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 3 ms 5100 KB Output isn't correct
2 Halted 0 ms 0 KB -