oj.uz

Submission #1111692

# Submission time Handle Problem Language Result Execution time Memory
1111692 2024-11-12T16:30:58 Z imarn Duathlon (APIO18_duathlon) C++14
0 / 100
 147 ms 114692 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(st.back()!=v){
                    gg[v+n].pb(st.back());
                    st.pop_back();
                }gg[v+n].pb(v);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 58 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 58 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 108 ms 109340 KB Output is correct
2 Correct 102 ms 109288 KB Output is correct
3 Incorrect 125 ms 109636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 94280 KB Output is correct
2 Correct 59 ms 94280 KB Output is correct
3 Correct 58 ms 94288 KB Output is correct
4 Correct 68 ms 94572 KB Output is correct
5 Correct 66 ms 94536 KB Output is correct
6 Correct 63 ms 94388 KB Output is correct
7 Correct 65 ms 94536 KB Output is correct
8 Correct 62 ms 94536 KB Output is correct
9 Correct 63 ms 94536 KB Output is correct
10 Incorrect 58 ms 94280 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 104520 KB Output is correct
2 Correct 112 ms 104520 KB Output is correct
3 Correct 125 ms 104520 KB Output is correct
4 Correct 127 ms 104520 KB Output is correct
5 Correct 147 ms 104580 KB Output is correct
6 Correct 142 ms 114692 KB Output is correct
7 Correct 139 ms 110992 KB Output is correct
8 Correct 131 ms 109384 KB Output is correct
9 Correct 124 ms 107988 KB Output is correct
10 Incorrect 134 ms 104520 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 94472 KB Output is correct
2 Correct 54 ms 94336 KB Output is correct
3 Correct 56 ms 94280 KB Output is correct
4 Correct 63 ms 94280 KB Output is correct
5 Correct 63 ms 94280 KB Output is correct
6 Correct 60 ms 94380 KB Output is correct
7 Correct 61 ms 94292 KB Output is correct
8 Correct 61 ms 94264 KB Output is correct
9 Correct 62 ms 94280 KB Output is correct
10 Correct 59 ms 94280 KB Output is correct
11 Correct 63 ms 94280 KB Output is correct
12 Correct 74 ms 94412 KB Output is correct
13 Correct 61 ms 94536 KB Output is correct
14 Correct 60 ms 94792 KB Output is correct
15 Correct 64 ms 94496 KB Output is correct
16 Incorrect 62 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 124 ms 104520 KB Output is correct
2 Correct 127 ms 104776 KB Output is correct
3 Correct 123 ms 104264 KB Output is correct
4 Correct 126 ms 103216 KB Output is correct
5 Correct 107 ms 101856 KB Output is correct
6 Correct 110 ms 101444 KB Output is correct
7 Correct 113 ms 101308 KB Output is correct
8 Correct 101 ms 100936 KB Output is correct
9 Correct 97 ms 100940 KB Output is correct
10 Correct 104 ms 100784 KB Output is correct
11 Correct 107 ms 100692 KB Output is correct
12 Correct 103 ms 100728 KB Output is correct
13 Correct 94 ms 100680 KB Output is correct
14 Correct 98 ms 102340 KB Output is correct
15 Correct 140 ms 111308 KB Output is correct
16 Correct 122 ms 108440 KB Output is correct
17 Correct 141 ms 109004 KB Output is correct
18 Correct 120 ms 107304 KB Output is correct
19 Incorrect 120 ms 103032 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 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 58 ms 94280 KB Output isn't correct
2 Halted 0 ms 0 KB -