oj.uz

답안 #981467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981467 2024-05-13T08:51:26 Z phoenix0423 철인 이종 경기 (APIO18_duathlon) C++17
71 / 100
 97 ms 32788 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;
        int cur = tsz * tsz * mid;
        // cout<<"add : "<<tsz<<" * "<<tsz<<"\n";
        cur -= lft * lft  * mid;
        // cout<<"ded : "<<lft<<" * "<<lft<<"\n";
        // ans -= lft * (lft - 1) * (tsz - lft);
        for(auto x : nadj[pos]){
            if(x == prev) continue;
            cur -= sz[x] * sz[x] * mid;
            // ans -= sz[x] * (sz[x] - 1) * (tsz - sz[x]);
        }
        ans += cur;
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 15960 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 4 ms 15936 KB Output is correct
4 Correct 3 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15756 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 3 ms 15708 KB Output is correct
9 Correct 3 ms 15940 KB Output is correct
10 Correct 4 ms 15708 KB Output is correct
11 Correct 4 ms 15808 KB Output is correct
12 Correct 4 ms 15704 KB Output is correct
13 Correct 4 ms 15936 KB Output is correct
14 Correct 3 ms 15708 KB Output is correct
15 Correct 3 ms 15708 KB Output is correct
16 Correct 3 ms 15708 KB Output is correct
17 Correct 3 ms 15708 KB Output is correct
18 Correct 3 ms 15932 KB Output is correct
19 Correct 3 ms 13660 KB Output is correct
20 Correct 3 ms 13656 KB Output is correct
21 Correct 3 ms 13660 KB Output is correct
22 Correct 3 ms 15708 KB Output is correct
23 Correct 3 ms 15708 KB Output is correct
24 Correct 3 ms 15704 KB Output is correct
25 Correct 3 ms 15708 KB Output is correct
26 Correct 3 ms 15708 KB Output is correct
27 Correct 3 ms 15708 KB Output is correct
28 Correct 3 ms 15708 KB Output is correct
29 Correct 3 ms 15816 KB Output is correct
30 Correct 3 ms 15708 KB Output is correct
31 Correct 3 ms 15936 KB Output is correct
32 Correct 4 ms 15708 KB Output is correct
33 Correct 4 ms 15708 KB Output is correct
34 Correct 3 ms 15708 KB Output is correct
35 Correct 3 ms 15708 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 15960 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 4 ms 15936 KB Output is correct
4 Correct 3 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15756 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 3 ms 15708 KB Output is correct
9 Correct 3 ms 15940 KB Output is correct
10 Correct 4 ms 15708 KB Output is correct
11 Correct 4 ms 15808 KB Output is correct
12 Correct 4 ms 15704 KB Output is correct
13 Correct 4 ms 15936 KB Output is correct
14 Correct 3 ms 15708 KB Output is correct
15 Correct 3 ms 15708 KB Output is correct
16 Correct 3 ms 15708 KB Output is correct
17 Correct 3 ms 15708 KB Output is correct
18 Correct 3 ms 15932 KB Output is correct
19 Correct 3 ms 13660 KB Output is correct
20 Correct 3 ms 13656 KB Output is correct
21 Correct 3 ms 13660 KB Output is correct
22 Correct 3 ms 15708 KB Output is correct
23 Correct 3 ms 15708 KB Output is correct
24 Correct 3 ms 15704 KB Output is correct
25 Correct 3 ms 15708 KB Output is correct
26 Correct 3 ms 15708 KB Output is correct
27 Correct 3 ms 15708 KB Output is correct
28 Correct 3 ms 15708 KB Output is correct
29 Correct 3 ms 15816 KB Output is correct
30 Correct 3 ms 15708 KB Output is correct
31 Correct 3 ms 15936 KB Output is correct
32 Correct 4 ms 15708 KB Output is correct
33 Correct 4 ms 15708 KB Output is correct
34 Correct 3 ms 15708 KB Output is correct
35 Correct 3 ms 15708 KB Output is correct
36 Correct 3 ms 13720 KB Output is correct
37 Correct 3 ms 15704 KB Output is correct
38 Correct 4 ms 15712 KB Output is correct
39 Incorrect 3 ms 15708 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 32452 KB Output is correct
2 Correct 52 ms 32708 KB Output is correct
3 Correct 63 ms 28620 KB Output is correct
4 Correct 63 ms 30724 KB Output is correct
5 Correct 64 ms 26240 KB Output is correct
6 Correct 60 ms 27556 KB Output is correct
7 Correct 56 ms 26064 KB Output is correct
8 Correct 57 ms 26492 KB Output is correct
9 Correct 69 ms 24660 KB Output is correct
10 Correct 56 ms 25192 KB Output is correct
11 Correct 44 ms 23048 KB Output is correct
12 Correct 45 ms 22864 KB Output is correct
13 Correct 42 ms 22868 KB Output is correct
14 Correct 50 ms 22608 KB Output is correct
15 Correct 51 ms 21736 KB Output is correct
16 Correct 33 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 15452 KB Output is correct
20 Correct 5 ms 15384 KB Output is correct
21 Correct 5 ms 15452 KB Output is correct
22 Correct 5 ms 15452 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16216 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 16172 KB Output is correct
5 Correct 4 ms 15964 KB Output is correct
6 Correct 4 ms 15964 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 4 ms 15964 KB Output is correct
9 Correct 4 ms 15964 KB Output is correct
10 Correct 4 ms 15964 KB Output is correct
11 Correct 3 ms 15964 KB Output is correct
12 Correct 4 ms 15964 KB Output is correct
13 Correct 4 ms 16072 KB Output is correct
14 Correct 4 ms 15964 KB Output is correct
15 Correct 5 ms 15960 KB Output is correct
16 Correct 4 ms 15984 KB Output is correct
17 Correct 4 ms 16216 KB Output is correct
18 Correct 4 ms 15964 KB Output is correct
19 Correct 4 ms 15936 KB Output is correct
20 Correct 4 ms 15964 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 25940 KB Output is correct
2 Correct 74 ms 27088 KB Output is correct
3 Correct 73 ms 27136 KB Output is correct
4 Correct 68 ms 27216 KB Output is correct
5 Correct 86 ms 27152 KB Output is correct
6 Correct 97 ms 32788 KB Output is correct
7 Correct 72 ms 31396 KB Output is correct
8 Correct 79 ms 30124 KB Output is correct
9 Correct 82 ms 29472 KB Output is correct
10 Correct 72 ms 27216 KB Output is correct
11 Correct 64 ms 27216 KB Output is correct
12 Correct 66 ms 27228 KB Output is correct
13 Correct 72 ms 27196 KB Output is correct
14 Correct 56 ms 26196 KB Output is correct
15 Correct 50 ms 25456 KB Output is correct
16 Correct 41 ms 22364 KB Output is correct
17 Correct 44 ms 27640 KB Output is correct
18 Correct 45 ms 27460 KB Output is correct
19 Correct 55 ms 27836 KB Output is correct
20 Correct 46 ms 27456 KB Output is correct

Subtask #6
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 15964 KB Output is correct
2 Correct 4 ms 15964 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 16048 KB Output is correct
6 Correct 4 ms 15964 KB Output is correct
7 Correct 4 ms 15964 KB Output is correct
8 Correct 3 ms 15884 KB Output is correct
9 Correct 3 ms 15964 KB Output is correct
10 Correct 3 ms 15896 KB Output is correct
11 Correct 5 ms 15964 KB Output is correct
12 Correct 4 ms 15944 KB Output is correct
13 Correct 4 ms 15964 KB Output is correct
14 Correct 4 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 15964 KB Output is correct
20 Correct 4 ms 15988 KB Output is correct
21 Correct 4 ms 15964 KB Output is correct
22 Correct 4 ms 15964 KB Output is correct
23 Correct 4 ms 15964 KB Output is correct
24 Correct 4 ms 15964 KB Output is correct
25 Correct 3 ms 13876 KB Output is correct
26 Correct 3 ms 15964 KB Output is correct
27 Correct 3 ms 13848 KB Output is correct

Subtask #7
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 25944 KB Output is correct
2 Correct 65 ms 26852 KB Output is correct
3 Correct 67 ms 26812 KB Output is correct
4 Correct 66 ms 25940 KB Output is correct
5 Correct 62 ms 24916 KB Output is correct
6 Correct 54 ms 24312 KB Output is correct
7 Correct 58 ms 24272 KB Output is correct
8 Correct 49 ms 23888 KB Output is correct
9 Correct 48 ms 23736 KB Output is correct
10 Correct 43 ms 23632 KB Output is correct
11 Correct 49 ms 23380 KB Output is correct
12 Correct 41 ms 23636 KB Output is correct
13 Correct 51 ms 23636 KB Output is correct
14 Correct 54 ms 25868 KB Output is correct
15 Correct 93 ms 31316 KB Output is correct
16 Correct 80 ms 29780 KB Output is correct
17 Correct 83 ms 30372 KB Output is correct
18 Correct 84 ms 28968 KB Output is correct
19 Correct 70 ms 25936 KB Output is correct
20 Correct 71 ms 25988 KB Output is correct
21 Correct 66 ms 25940 KB Output is correct
22 Correct 67 ms 25168 KB Output is correct
23 Correct 54 ms 24376 KB Output is correct
24 Correct 59 ms 26952 KB Output is correct
25 Correct 63 ms 27056 KB Output is correct
26 Correct 69 ms 26316 KB Output is correct
27 Correct 91 ms 26248 KB Output is correct

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 15960 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 4 ms 15936 KB Output is correct
4 Correct 3 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15756 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 3 ms 15708 KB Output is correct
9 Correct 3 ms 15940 KB Output is correct
10 Correct 4 ms 15708 KB Output is correct
11 Correct 4 ms 15808 KB Output is correct
12 Correct 4 ms 15704 KB Output is correct
13 Correct 4 ms 15936 KB Output is correct
14 Correct 3 ms 15708 KB Output is correct
15 Correct 3 ms 15708 KB Output is correct
16 Correct 3 ms 15708 KB Output is correct
17 Correct 3 ms 15708 KB Output is correct
18 Correct 3 ms 15932 KB Output is correct
19 Correct 3 ms 13660 KB Output is correct
20 Correct 3 ms 13656 KB Output is correct
21 Correct 3 ms 13660 KB Output is correct
22 Correct 3 ms 15708 KB Output is correct
23 Correct 3 ms 15708 KB Output is correct
24 Correct 3 ms 15704 KB Output is correct
25 Correct 3 ms 15708 KB Output is correct
26 Correct 3 ms 15708 KB Output is correct
27 Correct 3 ms 15708 KB Output is correct
28 Correct 3 ms 15708 KB Output is correct
29 Correct 3 ms 15816 KB Output is correct
30 Correct 3 ms 15708 KB Output is correct
31 Correct 3 ms 15936 KB Output is correct
32 Correct 4 ms 15708 KB Output is correct
33 Correct 4 ms 15708 KB Output is correct
34 Correct 3 ms 15708 KB Output is correct
35 Correct 3 ms 15708 KB Output is correct
36 Correct 3 ms 13720 KB Output is correct
37 Correct 3 ms 15704 KB Output is correct
38 Correct 4 ms 15712 KB Output is correct
39 Incorrect 3 ms 15708 KB Output isn't correct
40 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 15960 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 4 ms 15936 KB Output is correct
4 Correct 3 ms 15708 KB Output is correct
5 Correct 3 ms 15708 KB Output is correct
6 Correct 3 ms 15756 KB Output is correct
7 Correct 3 ms 15708 KB Output is correct
8 Correct 3 ms 15708 KB Output is correct
9 Correct 3 ms 15940 KB Output is correct
10 Correct 4 ms 15708 KB Output is correct
11 Correct 4 ms 15808 KB Output is correct
12 Correct 4 ms 15704 KB Output is correct
13 Correct 4 ms 15936 KB Output is correct
14 Correct 3 ms 15708 KB Output is correct
15 Correct 3 ms 15708 KB Output is correct
16 Correct 3 ms 15708 KB Output is correct
17 Correct 3 ms 15708 KB Output is correct
18 Correct 3 ms 15932 KB Output is correct
19 Correct 3 ms 13660 KB Output is correct
20 Correct 3 ms 13656 KB Output is correct
21 Correct 3 ms 13660 KB Output is correct
22 Correct 3 ms 15708 KB Output is correct
23 Correct 3 ms 15708 KB Output is correct
24 Correct 3 ms 15704 KB Output is correct
25 Correct 3 ms 15708 KB Output is correct
26 Correct 3 ms 15708 KB Output is correct
27 Correct 3 ms 15708 KB Output is correct
28 Correct 3 ms 15708 KB Output is correct
29 Correct 3 ms 15816 KB Output is correct
30 Correct 3 ms 15708 KB Output is correct
31 Correct 3 ms 15936 KB Output is correct
32 Correct 4 ms 15708 KB Output is correct
33 Correct 4 ms 15708 KB Output is correct
34 Correct 3 ms 15708 KB Output is correct
35 Correct 3 ms 15708 KB Output is correct
36 Correct 3 ms 13720 KB Output is correct
37 Correct 3 ms 15704 KB Output is correct
38 Correct 4 ms 15712 KB Output is correct
39 Incorrect 3 ms 15708 KB Output isn't correct
40 Halted 0 ms 0 KB -