oj.uz

Submission #370766

# Submission time Handle Problem Language Result Execution time Memory
370766 2021-02-24T14:54:59 Z Leonardo_Paes Duathlon (APIO18_duathlon) C++17
10 / 100
 1000 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] += 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 + 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]){
        assert(s.empty());
        for(int j=1; j<=n; j++) instack[j] = 0;
        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 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 20972 KB Output is correct
2 Correct 97 ms 20972 KB Output is correct
3 Correct 133 ms 20972 KB Output is correct
4 Correct 103 ms 20604 KB Output is correct
5 Correct 123 ms 18156 KB Output is correct
6 Correct 168 ms 20588 KB Output is correct
7 Correct 155 ms 19692 KB Output is correct
8 Correct 155 ms 20204 KB Output is correct
9 Correct 157 ms 18924 KB Output is correct
10 Correct 177 ms 18540 KB Output is correct
11 Execution timed out 1094 ms 12268 KB Time limit exceeded
12 Halted 0 ms 0 KB -

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 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 4 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 5 ms 5376 KB Output is correct
14 Correct 4 ms 5228 KB Output is correct
15 Correct 4 ms 5228 KB Output is correct
16 Correct 5 ms 5248 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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 22624 KB Output is correct
2 Correct 192 ms 22532 KB Output is correct
3 Correct 196 ms 22696 KB Output is correct
4 Correct 178 ms 22764 KB Output is correct
5 Correct 207 ms 22624 KB Output is correct
6 Correct 209 ms 26776 KB Output is correct
7 Correct 215 ms 25452 KB Output is correct
8 Correct 235 ms 24684 KB Output is correct
9 Correct 180 ms 24044 KB Output is correct
10 Correct 191 ms 22508 KB Output is correct
11 Correct 201 ms 22508 KB Output is correct
12 Correct 188 ms 22508 KB Output is correct
13 Correct 193 ms 22628 KB Output is correct
14 Correct 701 ms 21800 KB Output is correct
15 Execution timed out 1081 ms 14572 KB Time limit exceeded
16 Halted 0 ms 0 KB -

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 175 ms 22508 KB Output is correct
2 Correct 189 ms 22380 KB Output is correct
3 Incorrect 205 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 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 -