oj.uz

Submission #981493

# Submission time Handle Problem Language Result Execution time Memory
981493 2024-05-13T09:23:40 Z phoenix0423 Duathlon (APIO18_duathlon) C++17
71 / 100
 106 ms 32628 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){
    // cout<<"dfs : "<<pos<<"\n";
    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);
            low[pos] = min(low[pos], low[x]);
            if(low[x] >= in[pos]){
                int cur = n++;
                sq[cur] = 1, in[cur] = 1;
                while(low[st.top()] >= in[pos]){
                    if(st.top() == pos) break;
                    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();
                // cout<<"sz : "<<pos<<" "<<sz<<"\n";
                // for(auto x : nadj[cur]) cout<<x<<" ";
                // cout<<"\n";
            }
        }
    }
    // cout<<pos<<" "<<in[pos]<<" "<<low[pos]<<"\n";
}

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";
    // cout<<"sz : "<<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){
        // cout<<"do : "<<tsz<<"\n";
        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:37:21: warning: unused variable 'sz' [-Wunused-variable]
   37 |                 int sz = nadj[cur].size();
      |                     ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 3 ms 15708 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15708 KB Output is correct
7 Correct 3 ms 15944 KB Output is correct
8 Correct 3 ms 15704 KB Output is correct
9 Correct 3 ms 15708 KB Output is correct
10 Correct 3 ms 15944 KB Output is correct
11 Correct 3 ms 15704 KB Output is correct
12 Correct 4 ms 15708 KB Output is correct
13 Correct 3 ms 15708 KB Output is correct
14 Correct 4 ms 15708 KB Output is correct
15 Correct 3 ms 15708 KB Output is correct
16 Correct 3 ms 15704 KB Output is correct
17 Correct 4 ms 15708 KB Output is correct
18 Correct 3 ms 15888 KB Output is correct
19 Correct 3 ms 13656 KB Output is correct
20 Correct 3 ms 13660 KB Output is correct
21 Correct 3 ms 13660 KB Output is correct
22 Correct 3 ms 15704 KB Output is correct
23 Correct 3 ms 15708 KB Output is correct
24 Correct 4 ms 15708 KB Output is correct
25 Correct 4 ms 15708 KB Output is correct
26 Correct 3 ms 15940 KB Output is correct
27 Correct 5 ms 15708 KB Output is correct
28 Correct 3 ms 15708 KB Output is correct
29 Correct 3 ms 15708 KB Output is correct
30 Correct 3 ms 15708 KB Output is correct
31 Correct 3 ms 15940 KB Output is correct
32 Correct 3 ms 15708 KB Output is correct
33 Correct 3 ms 15708 KB Output is correct
34 Correct 4 ms 15800 KB Output is correct
35 Correct 3 ms 15708 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 3 ms 15708 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15708 KB Output is correct
7 Correct 3 ms 15944 KB Output is correct
8 Correct 3 ms 15704 KB Output is correct
9 Correct 3 ms 15708 KB Output is correct
10 Correct 3 ms 15944 KB Output is correct
11 Correct 3 ms 15704 KB Output is correct
12 Correct 4 ms 15708 KB Output is correct
13 Correct 3 ms 15708 KB Output is correct
14 Correct 4 ms 15708 KB Output is correct
15 Correct 3 ms 15708 KB Output is correct
16 Correct 3 ms 15704 KB Output is correct
17 Correct 4 ms 15708 KB Output is correct
18 Correct 3 ms 15888 KB Output is correct
19 Correct 3 ms 13656 KB Output is correct
20 Correct 3 ms 13660 KB Output is correct
21 Correct 3 ms 13660 KB Output is correct
22 Correct 3 ms 15704 KB Output is correct
23 Correct 3 ms 15708 KB Output is correct
24 Correct 4 ms 15708 KB Output is correct
25 Correct 4 ms 15708 KB Output is correct
26 Correct 3 ms 15940 KB Output is correct
27 Correct 5 ms 15708 KB Output is correct
28 Correct 3 ms 15708 KB Output is correct
29 Correct 3 ms 15708 KB Output is correct
30 Correct 3 ms 15708 KB Output is correct
31 Correct 3 ms 15940 KB Output is correct
32 Correct 3 ms 15708 KB Output is correct
33 Correct 3 ms 15708 KB Output is correct
34 Correct 4 ms 15800 KB Output is correct
35 Correct 3 ms 15708 KB Output is correct
36 Correct 3 ms 13660 KB Output is correct
37 Correct 3 ms 15708 KB Output is correct
38 Correct 3 ms 15708 KB Output is correct
39 Incorrect 3 ms 15936 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 32628 KB Output is correct
2 Correct 60 ms 32604 KB Output is correct
3 Correct 65 ms 28616 KB Output is correct
4 Correct 54 ms 30940 KB Output is correct
5 Correct 77 ms 26316 KB Output is correct
6 Correct 75 ms 27584 KB Output is correct
7 Correct 62 ms 26060 KB Output is correct
8 Correct 56 ms 26564 KB Output is correct
9 Correct 58 ms 24660 KB Output is correct
10 Correct 73 ms 25212 KB Output is correct
11 Correct 46 ms 23132 KB Output is correct
12 Correct 49 ms 22876 KB Output is correct
13 Correct 42 ms 22872 KB Output is correct
14 Correct 41 ms 22484 KB Output is correct
15 Correct 38 ms 21840 KB Output is correct
16 Correct 36 ms 21584 KB Output is correct
17 Correct 5 ms 15452 KB Output is correct
18 Correct 5 ms 15452 KB Output is correct
19 Correct 5 ms 15420 KB Output is correct
20 Correct 5 ms 15452 KB Output is correct
21 Correct 7 ms 15452 KB Output is correct
22 Correct 5 ms 15380 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15964 KB Output is correct
2 Correct 4 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 15960 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 3 ms 15964 KB Output is correct
9 Correct 4 ms 16032 KB Output is correct
10 Correct 4 ms 15964 KB Output is correct
11 Correct 4 ms 15960 KB Output is correct
12 Correct 4 ms 15964 KB Output is correct
13 Correct 4 ms 15964 KB Output is correct
14 Correct 4 ms 16000 KB Output is correct
15 Correct 4 ms 15964 KB Output is correct
16 Correct 3 ms 15964 KB Output is correct
17 Correct 3 ms 15896 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 66 ms 25940 KB Output is correct
2 Correct 70 ms 25940 KB Output is correct
3 Correct 74 ms 25928 KB Output is correct
4 Correct 82 ms 25936 KB Output is correct
5 Correct 88 ms 25900 KB Output is correct
6 Correct 82 ms 31572 KB Output is correct
7 Correct 96 ms 30024 KB Output is correct
8 Correct 77 ms 29012 KB Output is correct
9 Correct 104 ms 27768 KB Output is correct
10 Correct 67 ms 25828 KB Output is correct
11 Correct 78 ms 25972 KB Output is correct
12 Correct 71 ms 26008 KB Output is correct
13 Correct 90 ms 25984 KB Output is correct
14 Correct 73 ms 25436 KB Output is correct
15 Correct 60 ms 24392 KB Output is correct
16 Correct 32 ms 21852 KB Output is correct
17 Correct 54 ms 26256 KB Output is correct
18 Correct 52 ms 26180 KB Output is correct
19 Correct 60 ms 26484 KB Output is correct
20 Correct 72 ms 26436 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Correct 4 ms 15964 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 5 ms 15964 KB Output is correct
6 Correct 4 ms 15964 KB Output is correct
7 Correct 5 ms 15964 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 5 ms 15964 KB Output is correct
10 Correct 4 ms 15964 KB Output is correct
11 Correct 5 ms 15964 KB Output is correct
12 Correct 4 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 4 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 15988 KB Output is correct
20 Correct 4 ms 15964 KB Output is correct
21 Correct 4 ms 15964 KB Output is correct
22 Correct 3 ms 15988 KB Output is correct
23 Correct 4 ms 15960 KB Output is correct
24 Correct 5 ms 15964 KB Output is correct
25 Correct 3 ms 13916 KB Output is correct
26 Correct 4 ms 15972 KB Output is correct
27 Correct 3 ms 13924 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 26052 KB Output is correct
2 Correct 76 ms 25680 KB Output is correct
3 Correct 83 ms 25392 KB Output is correct
4 Correct 92 ms 24412 KB Output is correct
5 Correct 87 ms 23460 KB Output is correct
6 Correct 59 ms 22928 KB Output is correct
7 Correct 63 ms 22756 KB Output is correct
8 Correct 59 ms 22344 KB Output is correct
9 Correct 64 ms 22356 KB Output is correct
10 Correct 67 ms 22608 KB Output is correct
11 Correct 58 ms 22100 KB Output is correct
12 Correct 53 ms 22352 KB Output is correct
13 Correct 57 ms 22384 KB Output is correct
14 Correct 66 ms 24632 KB Output is correct
15 Correct 106 ms 29796 KB Output is correct
16 Correct 90 ms 28560 KB Output is correct
17 Correct 100 ms 28752 KB Output is correct
18 Correct 90 ms 27660 KB Output is correct
19 Correct 81 ms 24412 KB Output is correct
20 Correct 74 ms 24548 KB Output is correct
21 Correct 87 ms 24424 KB Output is correct
22 Correct 75 ms 23792 KB Output is correct
23 Correct 72 ms 23288 KB Output is correct
24 Correct 84 ms 25288 KB Output is correct
25 Correct 77 ms 25596 KB Output is correct
26 Correct 62 ms 24780 KB Output is correct
27 Correct 84 ms 24844 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 3 ms 15708 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15708 KB Output is correct
7 Correct 3 ms 15944 KB Output is correct
8 Correct 3 ms 15704 KB Output is correct
9 Correct 3 ms 15708 KB Output is correct
10 Correct 3 ms 15944 KB Output is correct
11 Correct 3 ms 15704 KB Output is correct
12 Correct 4 ms 15708 KB Output is correct
13 Correct 3 ms 15708 KB Output is correct
14 Correct 4 ms 15708 KB Output is correct
15 Correct 3 ms 15708 KB Output is correct
16 Correct 3 ms 15704 KB Output is correct
17 Correct 4 ms 15708 KB Output is correct
18 Correct 3 ms 15888 KB Output is correct
19 Correct 3 ms 13656 KB Output is correct
20 Correct 3 ms 13660 KB Output is correct
21 Correct 3 ms 13660 KB Output is correct
22 Correct 3 ms 15704 KB Output is correct
23 Correct 3 ms 15708 KB Output is correct
24 Correct 4 ms 15708 KB Output is correct
25 Correct 4 ms 15708 KB Output is correct
26 Correct 3 ms 15940 KB Output is correct
27 Correct 5 ms 15708 KB Output is correct
28 Correct 3 ms 15708 KB Output is correct
29 Correct 3 ms 15708 KB Output is correct
30 Correct 3 ms 15708 KB Output is correct
31 Correct 3 ms 15940 KB Output is correct
32 Correct 3 ms 15708 KB Output is correct
33 Correct 3 ms 15708 KB Output is correct
34 Correct 4 ms 15800 KB Output is correct
35 Correct 3 ms 15708 KB Output is correct
36 Correct 3 ms 13660 KB Output is correct
37 Correct 3 ms 15708 KB Output is correct
38 Correct 3 ms 15708 KB Output is correct
39 Incorrect 3 ms 15936 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15708 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 3 ms 15708 KB Output is correct
4 Correct 4 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15708 KB Output is correct
7 Correct 3 ms 15944 KB Output is correct
8 Correct 3 ms 15704 KB Output is correct
9 Correct 3 ms 15708 KB Output is correct
10 Correct 3 ms 15944 KB Output is correct
11 Correct 3 ms 15704 KB Output is correct
12 Correct 4 ms 15708 KB Output is correct
13 Correct 3 ms 15708 KB Output is correct
14 Correct 4 ms 15708 KB Output is correct
15 Correct 3 ms 15708 KB Output is correct
16 Correct 3 ms 15704 KB Output is correct
17 Correct 4 ms 15708 KB Output is correct
18 Correct 3 ms 15888 KB Output is correct
19 Correct 3 ms 13656 KB Output is correct
20 Correct 3 ms 13660 KB Output is correct
21 Correct 3 ms 13660 KB Output is correct
22 Correct 3 ms 15704 KB Output is correct
23 Correct 3 ms 15708 KB Output is correct
24 Correct 4 ms 15708 KB Output is correct
25 Correct 4 ms 15708 KB Output is correct
26 Correct 3 ms 15940 KB Output is correct
27 Correct 5 ms 15708 KB Output is correct
28 Correct 3 ms 15708 KB Output is correct
29 Correct 3 ms 15708 KB Output is correct
30 Correct 3 ms 15708 KB Output is correct
31 Correct 3 ms 15940 KB Output is correct
32 Correct 3 ms 15708 KB Output is correct
33 Correct 3 ms 15708 KB Output is correct
34 Correct 4 ms 15800 KB Output is correct
35 Correct 3 ms 15708 KB Output is correct
36 Correct 3 ms 13660 KB Output is correct
37 Correct 3 ms 15708 KB Output is correct
38 Correct 3 ms 15708 KB Output is correct
39 Incorrect 3 ms 15936 KB Output isn't correct
40 Halted 0 ms 0 KB -