oj.uz

Submission #739568

# Submission time Handle Problem Language Result Execution time Memory
739568 2023-05-10T16:29:25 Z bachhoangxuan Duathlon (APIO18_duathlon) C++17
0 / 100
 134 ms 32272 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
- insert(x)
- find_by_order(k): return iterator to the k-th smallest element
- order_of_key(x): the number of elements that are strictly smaller
*/
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define ld long double
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second
const int inf=1e18;
const int mod=1e9+7;
const int maxn=200005;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
int n,m,sz,pos,num[maxn],low[maxn];
vector<int> edge[maxn],adj[maxn],st;
int cnt[maxn],sum[maxn],cur,ans;
void add_edge(int u,int v){
    adj[u].push_back(v);
    adj[v].push_back(u);
    //cout << u << ' ' << v << '\n';
}
void dfs(int u,int par){
    low[u]=num[u]=++pos;
    st.push_back(u);
    for(int v:edge[u]){
        if(v==par) continue;
        if(!num[v]){
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=num[u]){
                sz++;
                while(st.back()!=v){
                    add_edge(st.back(),sz);
                    st.pop_back();
                }
                add_edge(v,sz);st.pop_back();
                add_edge(u,sz);
            }
        }
        else low[u]=min(low[u],num[v]);
    }
}
bool vis[maxn];
void dfs_sz(int u,int par){
    cur+=cnt[u];
    for(int v:adj[u]){
        if(v==par) continue;
        dfs_sz(v,u);
    }
}
void dfs_cal(int u,int par){
    vis[u]=true;sum[u]=cnt[u];
    int mul=(u<=n?1:(int)adj[u].size()-2),total=(cur-cnt[u])*(cur-cnt[u]);
    for(int v:adj[u]){
        if(v==par) continue;
        dfs_cal(v,u);sum[u]+=sum[v];
        total-=sum[v]*sum[v];
    }
    total-=(cur-sum[u])*(cur-sum[u]);
    ans+=mul*total;
    //cout << u << ' ' << sum[u] << '\n';
    //if(u>n){cout << u << ' ' << mul+2 << ' ' << total << '\n';}
}
void solve(){
    cin >> n >> m;sz=n;
    for(int i=1;i<=m;i++){
        int u,v;cin >> u >> v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        cnt[i]=1;
        if(!num[i]){
            dfs(i,0);sz++;
            while(!st.empty()){add_edge(st.back(),sz);st.pop_back();}
        }
    }
    for(int i=1;i<=sz;i++){
        if(!vis[i]){
            dfs_sz(i,0);
            //cout << cur << '\n';
            dfs_cal(i,0);
        }
    }
    cout << ans << '\n';
}
signed main(){
    //freopen("test_input.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test=1;//cin >> test;
    while(test--) solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9748 KB Output is correct
2 Correct 6 ms 9700 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9732 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9732 KB Output is correct
13 Correct 6 ms 9720 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9740 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9732 KB Output is correct
18 Correct 5 ms 9736 KB Output is correct
19 Incorrect 5 ms 9732 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9748 KB Output is correct
2 Correct 6 ms 9700 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9732 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9732 KB Output is correct
13 Correct 6 ms 9720 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9740 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9732 KB Output is correct
18 Correct 5 ms 9736 KB Output is correct
19 Incorrect 5 ms 9732 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 28508 KB Output is correct
2 Correct 90 ms 28620 KB Output is correct
3 Incorrect 85 ms 28468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9876 KB Output is correct
2 Correct 5 ms 9812 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 6 ms 9944 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 9940 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 7 ms 9940 KB Output is correct
10 Incorrect 6 ms 9812 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 24416 KB Output is correct
2 Correct 121 ms 24372 KB Output is correct
3 Correct 123 ms 24368 KB Output is correct
4 Correct 93 ms 24448 KB Output is correct
5 Correct 94 ms 24444 KB Output is correct
6 Correct 114 ms 32272 KB Output is correct
7 Correct 109 ms 30012 KB Output is correct
8 Correct 130 ms 28468 KB Output is correct
9 Correct 110 ms 27032 KB Output is correct
10 Incorrect 90 ms 24396 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 6 ms 9812 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 6 ms 9872 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9852 KB Output is correct
7 Correct 6 ms 9872 KB Output is correct
8 Correct 6 ms 9844 KB Output is correct
9 Correct 6 ms 9872 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 6 ms 9812 KB Output is correct
12 Correct 6 ms 9968 KB Output is correct
13 Correct 6 ms 9872 KB Output is correct
14 Correct 6 ms 9868 KB Output is correct
15 Correct 6 ms 9868 KB Output is correct
16 Incorrect 7 ms 9876 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 24396 KB Output is correct
2 Correct 114 ms 24092 KB Output is correct
3 Correct 102 ms 23888 KB Output is correct
4 Correct 132 ms 24464 KB Output is correct
5 Correct 130 ms 23296 KB Output is correct
6 Correct 107 ms 22772 KB Output is correct
7 Correct 110 ms 22576 KB Output is correct
8 Correct 93 ms 22172 KB Output is correct
9 Correct 83 ms 22092 KB Output is correct
10 Correct 88 ms 22036 KB Output is correct
11 Correct 74 ms 21836 KB Output is correct
12 Correct 89 ms 21860 KB Output is correct
13 Correct 84 ms 21888 KB Output is correct
14 Correct 127 ms 23740 KB Output is correct
15 Correct 129 ms 31316 KB Output is correct
16 Correct 134 ms 29308 KB Output is correct
17 Correct 118 ms 30020 KB Output is correct
18 Correct 131 ms 28260 KB Output is correct
19 Incorrect 118 ms 24620 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9748 KB Output is correct
2 Correct 6 ms 9700 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9732 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9732 KB Output is correct
13 Correct 6 ms 9720 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9740 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9732 KB Output is correct
18 Correct 5 ms 9736 KB Output is correct
19 Incorrect 5 ms 9732 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9748 KB Output is correct
2 Correct 6 ms 9700 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 7 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9732 KB Output is correct
10 Correct 5 ms 9684 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 6 ms 9732 KB Output is correct
13 Correct 6 ms 9720 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9740 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9732 KB Output is correct
18 Correct 5 ms 9736 KB Output is correct
19 Incorrect 5 ms 9732 KB Output isn't correct
20 Halted 0 ms 0 KB -