oj.uz

Submission #1094601

# Submission time Handle Problem Language Result Execution time Memory
1094601 2024-09-30T05:25:40 Z vjudge1 Duathlon (APIO18_duathlon) C++17
8 / 100
 55 ms 36836 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<long long,long long> PLL;
typedef long long LL;

#define int long long
#define ln '\n'
#define faster {ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);}

#define all(v) v.begin(),v.end()

int mod = 998244353;
const int N = 4e5 + 10;
const int inf = 1e9;


vector<PLL> g[N];
vector<int> comp[N];
int disc[N], low[N], mark[N], vis[N], timer = 1, cur = 1;
vector<int> currcomp;

void dfs(int u, int p){
    disc[u] = low[u] = timer++; currcomp.push_back(u);
    bool fl = 1;
    for(auto [v, id]: g[u]){
        if(v == p && fl) {fl = 0; continue;}
        if(disc[v]){
            low[u] = min(low[u], disc[v]);
        }else{
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if(disc[u] < low[v]){
                mark[id] = 1;
            }
        }
    }
}

void colorComponents(int u, int color){
    if(vis[u]) return;
    comp[color].push_back(u);
    vis[u] = color;
    for(auto [v, id]: g[u]){
        if(mark[id]) continue;
        colorComponents(v, color);
    }
}

void solve(int test){
    int n, m, q; cin>>n>>m;
    for(int i = 0, u, v; i < m; i++){
        cin>>u>>v;
        g[u].push_back({v, i}); g[v].push_back({u, i});
    }

    auto nC2 = [&](LL n){
        return n * (n - 1) / 2;
    };
    auto nC3 = [&](LL n){
        return n * (n - 1) * (n - 2) / 6;
    };
    LL ans = 0;
    for(int i = 1; i <= n; i++){
        if(!disc[i]){
            dfs(i, -1);
            int SZ = currcomp.size(), last = cur;
            ans += nC3(SZ);
            for(auto u: currcomp){
                if(!vis[u]){
                    colorComponents(u, cur++);
                }
            }
            currcomp.clear();
            for(int j = last; j < cur; j++){
                int sz = comp[j].size(); //cout<<sz<<'\n';
                LL tmp = nC3(sz) * 2 + nC2(sz - 1) * (SZ - sz);
                ans += tmp;
            }
        }
    }
    
    cout<<ans * 2<<'\n';
}

signed main(){
    faster
    int t = 1; 
    // cin>>t;
    for(int i = 1; i <= t; i++){
        solve(i);
    }
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void solve(long long int)':
count_triplets.cpp:52:15: warning: unused variable 'q' [-Wunused-variable]
   52 |     int n, m, q; cin>>n>>m;
      |               ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19236 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 8 ms 19288 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Incorrect 8 ms 19268 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19236 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 8 ms 19288 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Incorrect 8 ms 19268 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 36836 KB Output is correct
2 Correct 55 ms 36832 KB Output is correct
3 Correct 53 ms 33356 KB Output is correct
4 Correct 51 ms 35904 KB Output is correct
5 Correct 50 ms 31528 KB Output is correct
6 Correct 50 ms 32336 KB Output is correct
7 Correct 48 ms 31308 KB Output is correct
8 Correct 48 ms 32236 KB Output is correct
9 Correct 48 ms 30272 KB Output is correct
10 Correct 55 ms 30928 KB Output is correct
11 Correct 38 ms 28648 KB Output is correct
12 Correct 40 ms 28764 KB Output is correct
13 Correct 35 ms 28508 KB Output is correct
14 Correct 35 ms 28256 KB Output is correct
15 Correct 30 ms 27736 KB Output is correct
16 Correct 29 ms 27772 KB Output is correct
17 Correct 13 ms 24920 KB Output is correct
18 Correct 14 ms 24728 KB Output is correct
19 Correct 18 ms 24668 KB Output is correct
20 Correct 13 ms 24664 KB Output is correct
21 Correct 13 ms 24668 KB Output is correct
22 Correct 14 ms 24756 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19236 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 8 ms 19288 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Incorrect 8 ms 19268 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19036 KB Output is correct
2 Correct 9 ms 19236 KB Output is correct
3 Correct 8 ms 19036 KB Output is correct
4 Correct 8 ms 19036 KB Output is correct
5 Correct 8 ms 19288 KB Output is correct
6 Correct 9 ms 19036 KB Output is correct
7 Incorrect 8 ms 19268 KB Output isn't correct
8 Halted 0 ms 0 KB -