oj.uz

Submission #990603

# Submission time Handle Problem Language Result Execution time Memory
990603 2024-05-30T17:07:40 Z grogu Duathlon (APIO18_duathlon) C++14
66 / 100
 68 ms 31836 KB 
    // __builtin_popcount(x)
    // __builtin_popcountll(x)
    #define here cerr<<"===========================================\n"
    #include <bits/stdc++.h>
    #define ld double
    #define ll long long
    #define ull unsigned long long
    #define llinf 100000000000000000LL // 10^17
    #define iinf 2000000000 // 2*10^9
    #define pb push_back
    #define popb pop_back
    #define fi first
    #define sc second
    #define endl '\n'
    #define pii pair<int,int>
    #define pll pair<ll,ll>
    #define pld pair<ld,ld>
    #define sz(a) int(a.size())
    #define all(a) a.begin(),a.end()
    #define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
    using namespace std;
     
    #define maxn 200005
    ll n,m;
    vector<ll> g[maxn];
    vector<ll> v[maxn];
    ll low[maxn];
    ll in[maxn];
    bool vis[maxn];
    ll siz[maxn];
    ll it = 1;
    ll cnt = 1;
    ll comp = 0;
    stack<ll> st;
    void dfs(ll u,ll par){
        comp++;
        in[u] = it++;
        low[u] = in[u];
        st.push(u);
        for(ll s : g[u]){
            if(s==par) continue;
            if(in[s]){
                low[u] = min(low[u],low[s]);
            }else{
                dfs(s,u);
                low[u] = min(low[u],low[s]);
                if(low[s]>=in[u]){
                    v[u].pb(n+cnt);
                    while(sz(st)){
                        ll to = st.top();
                        st.pop();
                        v[n+cnt].pb(to);
                        if(to==s) break;
                    }
                    cnt++;
                }
            }
        }
     
    }
    ll ans = 0;
    ll f3(ll x){
        return x*(x-1)*(x-2);
    }
    ll f2(ll x){
        return x*(x-1);
    }
    void dfs2(ll u){
        if(u<=n) siz[u] = 1;
        for(ll s : v[u]){
            dfs2(s);
            siz[u]+=siz[s];
            if(u>n) ans-=f2(siz[s])*sz(v[u]);
        }
        if(u>n) ans-=f2(comp-siz[u])*sz(v[u]);
    }
    int main(){
    	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
        cin >> n >> m;
        for(ll i = 1;i<=m;i++){
            ll x,y; cin >> x >> y;
            g[x].pb(y);
            g[y].pb(x);
        }
        for(ll i = 1;i<=n;i++){
            if(in[i]==0){
                comp = 0;
                dfs(i,i);
                ans+=f3(comp);
                dfs2(i);
            }
        }
        cout<<ans<<endl;
    	return 0;
    }
    /*
    4 3
    1 2
    2 3
    3 4
    out: 8
    */
    /*
    4 4
    1 2
    2 3
    3 4
    4 2
    out: 14
    */

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12512 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 2 ms 12380 KB Output is correct
5 Correct 2 ms 12376 KB Output is correct
6 Correct 2 ms 12380 KB Output is correct
7 Correct 2 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 2 ms 12380 KB Output is correct
10 Correct 3 ms 12380 KB Output is correct
11 Correct 4 ms 12380 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 3 ms 12380 KB Output is correct
15 Correct 3 ms 12632 KB Output is correct
16 Correct 3 ms 12376 KB Output is correct
17 Correct 3 ms 12380 KB Output is correct
18 Correct 2 ms 12380 KB Output is correct
19 Correct 2 ms 12380 KB Output is correct
20 Correct 2 ms 12380 KB Output is correct
21 Correct 3 ms 12380 KB Output is correct
22 Incorrect 2 ms 12380 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12512 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 2 ms 12380 KB Output is correct
5 Correct 2 ms 12376 KB Output is correct
6 Correct 2 ms 12380 KB Output is correct
7 Correct 2 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 2 ms 12380 KB Output is correct
10 Correct 3 ms 12380 KB Output is correct
11 Correct 4 ms 12380 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 3 ms 12380 KB Output is correct
15 Correct 3 ms 12632 KB Output is correct
16 Correct 3 ms 12376 KB Output is correct
17 Correct 3 ms 12380 KB Output is correct
18 Correct 2 ms 12380 KB Output is correct
19 Correct 2 ms 12380 KB Output is correct
20 Correct 2 ms 12380 KB Output is correct
21 Correct 3 ms 12380 KB Output is correct
22 Incorrect 2 ms 12380 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 29104 KB Output is correct
2 Correct 54 ms 29212 KB Output is correct
3 Correct 52 ms 27160 KB Output is correct
4 Correct 47 ms 28616 KB Output is correct
5 Correct 44 ms 24136 KB Output is correct
6 Correct 45 ms 26708 KB Output is correct
7 Correct 42 ms 25480 KB Output is correct
8 Correct 52 ms 25824 KB Output is correct
9 Correct 39 ms 23892 KB Output is correct
10 Correct 43 ms 23728 KB Output is correct
11 Correct 45 ms 21596 KB Output is correct
12 Correct 50 ms 21340 KB Output is correct
13 Correct 45 ms 21072 KB Output is correct
14 Correct 32 ms 21076 KB Output is correct
15 Correct 22 ms 20232 KB Output is correct
16 Correct 25 ms 19856 KB Output is correct
17 Correct 4 ms 14428 KB Output is correct
18 Correct 4 ms 14428 KB Output is correct
19 Correct 5 ms 14428 KB Output is correct
20 Correct 5 ms 14428 KB Output is correct
21 Correct 5 ms 14428 KB Output is correct
22 Correct 5 ms 14428 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 4 ms 12476 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 3 ms 12636 KB Output is correct
6 Correct 3 ms 12632 KB Output is correct
7 Correct 3 ms 12636 KB Output is correct
8 Correct 2 ms 12636 KB Output is correct
9 Correct 3 ms 12636 KB Output is correct
10 Correct 3 ms 12556 KB Output is correct
11 Correct 2 ms 12636 KB Output is correct
12 Correct 3 ms 12632 KB Output is correct
13 Correct 3 ms 12632 KB Output is correct
14 Correct 3 ms 12632 KB Output is correct
15 Correct 3 ms 12380 KB Output is correct
16 Correct 3 ms 12380 KB Output is correct
17 Correct 3 ms 12636 KB Output is correct
18 Correct 3 ms 12636 KB Output is correct
19 Correct 3 ms 12520 KB Output is correct
20 Correct 2 ms 12512 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 24508 KB Output is correct
2 Correct 43 ms 24536 KB Output is correct
3 Correct 40 ms 24456 KB Output is correct
4 Correct 47 ms 24364 KB Output is correct
5 Correct 43 ms 24400 KB Output is correct
6 Correct 53 ms 31836 KB Output is correct
7 Correct 51 ms 29444 KB Output is correct
8 Correct 49 ms 27984 KB Output is correct
9 Correct 68 ms 26880 KB Output is correct
10 Correct 38 ms 24400 KB Output is correct
11 Correct 41 ms 24344 KB Output is correct
12 Correct 64 ms 24400 KB Output is correct
13 Correct 47 ms 24476 KB Output is correct
14 Correct 36 ms 23688 KB Output is correct
15 Correct 32 ms 22868 KB Output is correct
16 Correct 23 ms 20356 KB Output is correct
17 Correct 27 ms 23492 KB Output is correct
18 Correct 27 ms 23504 KB Output is correct
19 Correct 29 ms 23928 KB Output is correct
20 Correct 29 ms 23620 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 4 ms 12516 KB Output is correct
3 Correct 3 ms 12524 KB Output is correct
4 Correct 3 ms 12380 KB Output is correct
5 Correct 3 ms 12380 KB Output is correct
6 Correct 3 ms 12380 KB Output is correct
7 Correct 3 ms 12512 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 3 ms 12380 KB Output is correct
10 Correct 3 ms 12380 KB Output is correct
11 Correct 3 ms 12520 KB Output is correct
12 Correct 3 ms 12524 KB Output is correct
13 Correct 3 ms 12636 KB Output is correct
14 Correct 3 ms 12516 KB Output is correct
15 Correct 3 ms 12636 KB Output is correct
16 Correct 4 ms 12380 KB Output is correct
17 Correct 3 ms 12528 KB Output is correct
18 Correct 3 ms 12380 KB Output is correct
19 Correct 3 ms 12536 KB Output is correct
20 Correct 3 ms 12380 KB Output is correct
21 Correct 3 ms 12636 KB Output is correct
22 Correct 4 ms 12636 KB Output is correct
23 Correct 3 ms 12632 KB Output is correct
24 Correct 3 ms 12636 KB Output is correct
25 Correct 2 ms 12572 KB Output is correct
26 Correct 2 ms 12512 KB Output is correct
27 Correct 3 ms 12376 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 24400 KB Output is correct
2 Correct 42 ms 24404 KB Output is correct
3 Correct 52 ms 24016 KB Output is correct
4 Correct 50 ms 23048 KB Output is correct
5 Correct 43 ms 21584 KB Output is correct
6 Correct 39 ms 20836 KB Output is correct
7 Correct 37 ms 20564 KB Output is correct
8 Correct 34 ms 20048 KB Output is correct
9 Correct 36 ms 19792 KB Output is correct
10 Correct 33 ms 19640 KB Output is correct
11 Correct 47 ms 19648 KB Output is correct
12 Correct 31 ms 19536 KB Output is correct
13 Correct 31 ms 19436 KB Output is correct
14 Correct 34 ms 21840 KB Output is correct
15 Correct 67 ms 28888 KB Output is correct
16 Correct 48 ms 27380 KB Output is correct
17 Correct 46 ms 27732 KB Output is correct
18 Correct 50 ms 26252 KB Output is correct
19 Correct 43 ms 23004 KB Output is correct
20 Correct 49 ms 22872 KB Output is correct
21 Correct 55 ms 23012 KB Output is correct
22 Correct 40 ms 22016 KB Output is correct
23 Correct 51 ms 21332 KB Output is correct
24 Correct 41 ms 23616 KB Output is correct
25 Correct 41 ms 23756 KB Output is correct
26 Correct 42 ms 22940 KB Output is correct
27 Correct 44 ms 22960 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12512 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 2 ms 12380 KB Output is correct
5 Correct 2 ms 12376 KB Output is correct
6 Correct 2 ms 12380 KB Output is correct
7 Correct 2 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 2 ms 12380 KB Output is correct
10 Correct 3 ms 12380 KB Output is correct
11 Correct 4 ms 12380 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 3 ms 12380 KB Output is correct
15 Correct 3 ms 12632 KB Output is correct
16 Correct 3 ms 12376 KB Output is correct
17 Correct 3 ms 12380 KB Output is correct
18 Correct 2 ms 12380 KB Output is correct
19 Correct 2 ms 12380 KB Output is correct
20 Correct 2 ms 12380 KB Output is correct
21 Correct 3 ms 12380 KB Output is correct
22 Incorrect 2 ms 12380 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12512 KB Output is correct
2 Correct 2 ms 12380 KB Output is correct
3 Correct 4 ms 12380 KB Output is correct
4 Correct 2 ms 12380 KB Output is correct
5 Correct 2 ms 12376 KB Output is correct
6 Correct 2 ms 12380 KB Output is correct
7 Correct 2 ms 12380 KB Output is correct
8 Correct 3 ms 12380 KB Output is correct
9 Correct 2 ms 12380 KB Output is correct
10 Correct 3 ms 12380 KB Output is correct
11 Correct 4 ms 12380 KB Output is correct
12 Correct 3 ms 12380 KB Output is correct
13 Correct 4 ms 12380 KB Output is correct
14 Correct 3 ms 12380 KB Output is correct
15 Correct 3 ms 12632 KB Output is correct
16 Correct 3 ms 12376 KB Output is correct
17 Correct 3 ms 12380 KB Output is correct
18 Correct 2 ms 12380 KB Output is correct
19 Correct 2 ms 12380 KB Output is correct
20 Correct 2 ms 12380 KB Output is correct
21 Correct 3 ms 12380 KB Output is correct
22 Incorrect 2 ms 12380 KB Output isn't correct
23 Halted 0 ms 0 KB -