oj.uz

Submission #370839

# Submission time Handle Problem Language Result Execution time Memory
370839 2021-02-24T18:14:07 Z Leonardo_Paes Duathlon (APIO18_duathlon) C++17
0 / 100
 1000 ms 28124 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(2);
    }
    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
0 / 8.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5236 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 4 ms 5356 KB Output is correct
6 Correct 5 ms 5228 KB Output is correct
7 Correct 4 ms 5356 KB Output is correct
8 Correct 4 ms 5356 KB Output is correct
9 Correct 4 ms 5228 KB Output is correct
10 Incorrect 6 ms 5228 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 22508 KB Output is correct
2 Correct 167 ms 22508 KB Output is correct
3 Correct 184 ms 22508 KB Output is correct
4 Correct 167 ms 22528 KB Output is correct
5 Correct 175 ms 22508 KB Output is correct
6 Correct 225 ms 28124 KB Output is correct
7 Correct 193 ms 26348 KB Output is correct
8 Correct 196 ms 25324 KB Output is correct
9 Correct 169 ms 24300 KB Output is correct
10 Execution timed out 1093 ms 22508 KB Time limit exceeded
11 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 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 174 ms 22508 KB Output is correct
2 Correct 187 ms 22380 KB Output is correct
3 Incorrect 167 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 -