oj.uz

Submission #981435

# Submission time Handle Problem Language Result Execution time Memory
981435 2024-05-13T08:10:17 Z phoenix0423 Duathlon (APIO18_duathlon) C++17
23 / 100
 113 ms 37392 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
const int maxn = 2e5 + 5;
vector<int> adj[maxn], nadj[maxn];
int in[maxn], low[maxn], sq[maxn], sz[maxn], dfn = 0, cnt = 0;
int n, m, ans = 0;
stack<int> st;

void dfs(int pos){
    in[pos] = low[pos] = ++dfn;
    st.push(pos);
    for(auto x : adj[pos]){
        if(in[x]) low[pos] = min(low[pos], in[x]);
        else{
            dfs(x);
            if(low[x] >= in[pos]){
                int cur = n++;
                sq[cur] = 1, in[cur] = 1;
                while(st.top() != pos){
                    nadj[cur].pb(st.top());
                    nadj[st.top()].pb(cur);
                    st.pop();
                }
                nadj[cur].pb(pos);
                nadj[pos].pb(cur);
                int sz = nadj[cur].size();
            }
        }
    }
}

void dfs2(int pos, int prev){
    sz[pos] = 1 - sq[pos];
    for(auto x : nadj[pos]){
        if(x == prev) continue;
        dfs2(x, pos);
        sz[pos] += sz[x];
    }
}

void dfs3(int pos, int prev, int tsz){
    // cout<<"d : "<<tsz<<" "<<pos<<" "<<sz[pos]<<"\n";
    if(!sq[pos]){
        ans += (tsz - 1) * (tsz - 1);
        ans -= (tsz - sz[pos]) * (tsz - sz[pos]);
        for(auto x : nadj[pos]){
            if(x == prev) continue;
            ans -= sz[x] * sz[x];
        }
    }
    else if(nadj[pos].size() >= 3){
        int lft = tsz - sz[pos], mid = nadj[pos].size() - 2;
        ans += tsz * tsz * mid;
        ans -= lft * lft  * mid;
        for(auto x : nadj[pos]){
            if(x == prev) continue;
            ans -= sz[x] * sz[x] * mid;
        }
    }
    for(auto x : nadj[pos]){
        if(x == prev) continue;
        dfs3(x, pos, tsz);
    }
}

signed main(void){
    fastio;
    cin>>n>>m;
    for(int i = 0; i < m; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    for(int i = 0; i < n; i++){
        if(!in[i]){
            dfs(i);
            dfs2(i, -1);
            dfs3(i, -1, sz[i]);
        }
    }
    cout<<ans<<"\n";

}

Compilation message

count_triplets.cpp: In function 'void dfs(long long int)':
count_triplets.cpp:34:21: warning: unused variable 'sz' [-Wunused-variable]
   34 |                 int sz = nadj[cur].size();
      |                     ^~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 5 ms 15960 KB Output is correct
3 Correct 4 ms 15960 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 3 ms 15964 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 5 ms 15964 KB Output is correct
9 Correct 4 ms 15964 KB Output is correct
10 Correct 4 ms 15960 KB Output is correct
11 Correct 4 ms 15960 KB Output is correct
12 Correct 3 ms 15964 KB Output is correct
13 Correct 4 ms 15964 KB Output is correct
14 Correct 5 ms 15964 KB Output is correct
15 Correct 3 ms 15964 KB Output is correct
16 Correct 4 ms 15964 KB Output is correct
17 Correct 4 ms 15964 KB Output is correct
18 Correct 4 ms 15964 KB Output is correct
19 Correct 4 ms 15964 KB Output is correct
20 Correct 4 ms 15964 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 25872 KB Output is correct
2 Correct 95 ms 27300 KB Output is correct
3 Correct 98 ms 27288 KB Output is correct
4 Correct 73 ms 27216 KB Output is correct
5 Correct 82 ms 27152 KB Output is correct
6 Correct 111 ms 32872 KB Output is correct
7 Correct 84 ms 31316 KB Output is correct
8 Correct 78 ms 30284 KB Output is correct
9 Correct 113 ms 29356 KB Output is correct
10 Correct 110 ms 27216 KB Output is correct
11 Correct 94 ms 27220 KB Output is correct
12 Correct 65 ms 27220 KB Output is correct
13 Correct 108 ms 27148 KB Output is correct
14 Correct 101 ms 26196 KB Output is correct
15 Correct 74 ms 25424 KB Output is correct
16 Correct 66 ms 22424 KB Output is correct
17 Correct 68 ms 27592 KB Output is correct
18 Correct 51 ms 27460 KB Output is correct
19 Correct 48 ms 27804 KB Output is correct
20 Correct 68 ms 27456 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15960 KB Output is correct
2 Correct 4 ms 15960 KB Output is correct
3 Incorrect 4 ms 15964 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 25940 KB Output is correct
2 Correct 63 ms 26964 KB Output is correct
3 Incorrect 68 ms 26728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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