oj.uz

Submission #1111691

# Submission time Handle Problem Language Result Execution time Memory
1111691 2024-11-12T16:29:09 Z imarn Duathlon (APIO18_duathlon) C++14
0 / 100
 137 ms 115912 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=2e6+5;
vector<int>h,g[mxn],st;
vector<int>gg[mxn];
bool vis[mxn]{0};
int di[mxn]{0},lo[mxn]{0},cur=0;
ll cnt=0,n;
ll sz[mxn]{0};
void dfs(int u,int p){
    di[u]=lo[u]=++cur;
    st.pb(u);cnt++;
    for(auto v:g[u]){
        if(!di[v]){
            dfs(v,u);
            lo[u]=min(lo[u],lo[v]);
            if(lo[v]>=di[u]){
                while(gg[v+n].empty()||gg[v+n].back()!=v){
                    gg[v+n].pb(st.back());
                    st.pop_back();
                }
                gg[u].pb(v+n);
            }
        }else if(v!=p){
            lo[u]=min(lo[u],di[v]);
        }
    }
}ll rs=0;
void solve(int u,int p){
    if(u<=n)sz[u]=1;
    for(auto v:gg[u]){
        if(v==p)continue;
        solve(v,u);sz[u]+=sz[v];
        if(u>n)rs-=sz(gg[u])*(sz[v])*(sz[v]-1);
    }
    if(u>n)rs-=sz(gg[u])*(n-sz[u])*(n-sz[u]-1);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int m;cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;g[a].pb(b);g[b].pb(a);
    }
    for(int i=1;i<=n;i++){
        if(di[i])continue;cnt=0;
        dfs(i,i);st.clear();
        rs+=cnt*(cnt-1)*(cnt-2);
        solve(i,i);
    }cout<<rs;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:58:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   58 |         if(di[i])continue;cnt=0;
      |         ^~
count_triplets.cpp:58:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   58 |         if(di[i])continue;cnt=0;
      |                           ^~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 110568 KB Output is correct
2 Correct 101 ms 110408 KB Output is correct
3 Incorrect 129 ms 109700 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 94468 KB Output is correct
2 Correct 62 ms 94424 KB Output is correct
3 Correct 64 ms 94300 KB Output is correct
4 Correct 59 ms 94536 KB Output is correct
5 Correct 58 ms 94536 KB Output is correct
6 Correct 74 ms 94536 KB Output is correct
7 Correct 73 ms 94440 KB Output is correct
8 Correct 61 ms 94536 KB Output is correct
9 Correct 63 ms 94536 KB Output is correct
10 Incorrect 64 ms 94572 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 105768 KB Output is correct
2 Correct 124 ms 105800 KB Output is correct
3 Correct 125 ms 105784 KB Output is correct
4 Correct 111 ms 104524 KB Output is correct
5 Correct 116 ms 105924 KB Output is correct
6 Correct 130 ms 115912 KB Output is correct
7 Correct 134 ms 112328 KB Output is correct
8 Correct 122 ms 110656 KB Output is correct
9 Correct 137 ms 107848 KB Output is correct
10 Incorrect 105 ms 107336 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94280 KB Output is correct
2 Correct 56 ms 94440 KB Output is correct
3 Correct 58 ms 94300 KB Output is correct
4 Correct 56 ms 94280 KB Output is correct
5 Correct 56 ms 94280 KB Output is correct
6 Correct 56 ms 94280 KB Output is correct
7 Correct 52 ms 94280 KB Output is correct
8 Correct 53 ms 94280 KB Output is correct
9 Correct 53 ms 94280 KB Output is correct
10 Correct 58 ms 94308 KB Output is correct
11 Correct 65 ms 94280 KB Output is correct
12 Correct 63 ms 94536 KB Output is correct
13 Correct 59 ms 94444 KB Output is correct
14 Correct 74 ms 94400 KB Output is correct
15 Correct 62 ms 94540 KB Output is correct
16 Incorrect 60 ms 94284 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 105800 KB Output is correct
2 Correct 123 ms 106100 KB Output is correct
3 Correct 126 ms 105544 KB Output is correct
4 Correct 113 ms 104520 KB Output is correct
5 Correct 116 ms 103356 KB Output is correct
6 Correct 123 ms 102984 KB Output is correct
7 Correct 110 ms 102476 KB Output is correct
8 Correct 105 ms 102224 KB Output is correct
9 Correct 98 ms 102256 KB Output is correct
10 Correct 93 ms 101960 KB Output is correct
11 Correct 111 ms 101968 KB Output is correct
12 Correct 116 ms 101780 KB Output is correct
13 Correct 102 ms 101912 KB Output is correct
14 Correct 100 ms 103732 KB Output is correct
15 Correct 127 ms 112072 KB Output is correct
16 Correct 129 ms 109896 KB Output is correct
17 Correct 121 ms 110544 KB Output is correct
18 Correct 129 ms 108524 KB Output is correct
19 Incorrect 120 ms 104600 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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