oj.uz

Submission #572181

# Submission time Handle Problem Language Result Execution time Memory
572181 2022-06-03T23:02:39 Z somo Duathlon (APIO18_duathlon) C++14
66 / 100
 421 ms 89504 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll,ll>
#define F first
#define S second
#define double long double
#define all(x) (x).begin(),(x).end()

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll , null_type , less_equal<ll> ,rb_tree_tag ,tree_order_statistics_node_update >ordered_set;

const int MOD = 1e9 + 7 ;
const int  N= 5e5 + 10;
const ll INF= 1e18+10;

struct trp{ll F,S,T;};

ll po(ll x,ll y)
{
    ll ans = 1;
    while(y){
        if( y & 1 ) ans *=x;
        y /= 2;
        x *=x;
        //ans %= MOD;
        //x %= MOD;
    }
    return ans;
}

ll ans;
ll sz[N];
ll val[N];
ll ctr = 1;
ll node[N];
bool vis[N];
ll n , m, nn ;
vector<ll>v[N];
map<pii,bool>mp;
vector<ll>com[N];
ll tin[N],low[N];
vector<ll>tree1[N];
vector<ll>no_name[N];

void dfs_br(ll x,ll p)
{
    tin[x] = low[x] = ctr ++;
    for(auto i : v[x]){
        if(i == p) continue;
        if(!tin[i]){
            dfs_br(i,x);
            low[x] = min(low[x], low[i]);
            if(low[i] > tin[x]){
                mp[{x,i}] = 1;
                mp[{i,x}] = 1;
            }
        }
        else low[x] = min(low[x] , tin[i]);
    }
}

void dfs(ll x)
{
    com[ctr].pb(x);
    node[x] = ctr;
    val[ctr] ++;
    for(auto i : v[x]){
        if(mp[{x,i}]){
            if(node[i]){
                no_name[i].pb(node[x]);
                no_name[x].pb(node[i]);
                tree1[node[x]].pb(node[i]);
                tree1[node[i]].pb(node[x]);
            }
        }
        else{
            if(!node[i]) dfs(i);
        }
    }
}

void dfs_tr(ll x)
{
    vis[x] = 1;
    for(auto i : tree1[x]){
        if(!vis[i]){
            dfs_tr(i);
            sz[x] += sz[i];
        }
    }
    sz[x] += val[x];
}

void dfs_get(ll x)
{
    vis[x] = 1;
    if(val[x] >= 3) ans += val[x] * (val[x]-1) * (val[x]-2);
    ll curr = 0;
    ll h = (val[x] >= 2 ? (val[x]-1)*(val[x]-1) : 0);
    vector<ll>g;
    for(auto i : com[x]){
        ll sm = 0;
        for(auto j : no_name[i]){
            if(vis[j]) sm += nn-sz[x];
            else sm += sz[j];
        }
        if(sm) g.pb(sm);
    }

    if(g.size() > 1){
        ll sm = g[0];
        for(ll i= 1; i < g.size() ; i ++){
            curr += g[i] * sm;
            sm += g[i];
        }
        ans += curr*2*val[x];
    }

    for(auto i : com[x]){
        vector<ll>gg;
        for(auto j : no_name[i]){
            if(vis[j]) gg.pb(nn-sz[x]);
            else gg.pb(sz[j]);
        }
        if(gg.size() > 1){
            ll smm = gg[0];
            ll b = 0;
            for(ll j = 1 ; j < gg.size() ; j ++){
                b += gg[j] * smm;
                smm += gg[j];
            }
            ans += b * 2;
        }
    }

    for(auto i : tree1[x]){
        if(vis[i]){
            ans += h * (nn-sz[x]) * 2;
        }
        else{
            ans += h * sz[i] * 2;
            dfs_get(i);
        }
    }
}

void solve()
{
    cin >> n >> m;
    for(ll i= 1; i <= m; i ++){
        ll x,y;
        cin >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
    }
    for(int  i= 1; i <= n; i ++){
        if(!tin[i]) dfs_br(i,i);
    }
    ctr = 1;
    for(ll i= 1; i <= n ; i ++){
        if(!node[i]) dfs(i),ctr ++;
    }
    ctr --;
    for(ll i= 1; i <= ctr; i ++){
        if(!vis[i]) dfs_tr(i);
    }
    for(ll i= 1; i <= ctr ; i ++) vis[i] = 0;
    for(ll i= 1; i <= ctr ; i ++){
        if(!vis[i]){
            nn = sz[i];
            dfs_get(i);
        }
    }
    cout << ans << endl;
}

int main(){
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//freopen(".in" , "r" , stdin);freopen(".out" , "w" , stdout);
	int t = 1;
    //cin >> t;
	while(t--) {solve() ; }
}

Compilation message

count_triplets.cpp: In function 'void dfs_get(long long int)':
count_triplets.cpp:118:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(ll i= 1; i < g.size() ; i ++){
      |                      ~~^~~~~~~~~~
count_triplets.cpp:134:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |             for(ll j = 1 ; j < gg.size() ; j ++){
      |                            ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47272 KB Output is correct
2 Correct 23 ms 47316 KB Output is correct
3 Correct 23 ms 47308 KB Output is correct
4 Correct 24 ms 47188 KB Output is correct
5 Correct 23 ms 47268 KB Output is correct
6 Correct 28 ms 47188 KB Output is correct
7 Correct 24 ms 47188 KB Output is correct
8 Incorrect 23 ms 47316 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47272 KB Output is correct
2 Correct 23 ms 47316 KB Output is correct
3 Correct 23 ms 47308 KB Output is correct
4 Correct 24 ms 47188 KB Output is correct
5 Correct 23 ms 47268 KB Output is correct
6 Correct 28 ms 47188 KB Output is correct
7 Correct 24 ms 47188 KB Output is correct
8 Incorrect 23 ms 47316 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 78780 KB Output is correct
2 Correct 279 ms 78840 KB Output is correct
3 Correct 287 ms 80468 KB Output is correct
4 Correct 247 ms 79676 KB Output is correct
5 Correct 275 ms 76536 KB Output is correct
6 Correct 306 ms 80280 KB Output is correct
7 Correct 325 ms 77636 KB Output is correct
8 Correct 357 ms 78272 KB Output is correct
9 Correct 320 ms 75704 KB Output is correct
10 Correct 322 ms 75440 KB Output is correct
11 Correct 223 ms 71136 KB Output is correct
12 Correct 246 ms 70764 KB Output is correct
13 Correct 250 ms 70324 KB Output is correct
14 Correct 228 ms 69836 KB Output is correct
15 Correct 180 ms 67788 KB Output is correct
16 Correct 190 ms 67368 KB Output is correct
17 Correct 34 ms 54428 KB Output is correct
18 Correct 34 ms 54444 KB Output is correct
19 Correct 34 ms 54476 KB Output is correct
20 Correct 37 ms 54484 KB Output is correct
21 Correct 33 ms 54476 KB Output is correct
22 Correct 33 ms 54348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 47568 KB Output is correct
2 Correct 25 ms 47584 KB Output is correct
3 Correct 27 ms 47532 KB Output is correct
4 Correct 25 ms 47700 KB Output is correct
5 Correct 28 ms 47600 KB Output is correct
6 Correct 25 ms 47652 KB Output is correct
7 Correct 26 ms 47636 KB Output is correct
8 Correct 24 ms 47676 KB Output is correct
9 Correct 25 ms 47632 KB Output is correct
10 Correct 26 ms 47576 KB Output is correct
11 Correct 27 ms 47544 KB Output is correct
12 Correct 25 ms 47516 KB Output is correct
13 Correct 25 ms 47572 KB Output is correct
14 Correct 24 ms 47544 KB Output is correct
15 Correct 24 ms 47528 KB Output is correct
16 Correct 24 ms 47412 KB Output is correct
17 Correct 26 ms 47536 KB Output is correct
18 Correct 25 ms 47572 KB Output is correct
19 Correct 25 ms 47544 KB Output is correct
20 Correct 25 ms 47564 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 78436 KB Output is correct
2 Correct 363 ms 79528 KB Output is correct
3 Correct 341 ms 79344 KB Output is correct
4 Correct 346 ms 79568 KB Output is correct
5 Correct 337 ms 79564 KB Output is correct
6 Correct 400 ms 89504 KB Output is correct
7 Correct 375 ms 86816 KB Output is correct
8 Correct 370 ms 84744 KB Output is correct
9 Correct 421 ms 82800 KB Output is correct
10 Correct 353 ms 79436 KB Output is correct
11 Correct 412 ms 79448 KB Output is correct
12 Correct 372 ms 79436 KB Output is correct
13 Correct 363 ms 79352 KB Output is correct
14 Correct 319 ms 77300 KB Output is correct
15 Correct 288 ms 75256 KB Output is correct
16 Correct 175 ms 68504 KB Output is correct
17 Correct 306 ms 81504 KB Output is correct
18 Correct 299 ms 80812 KB Output is correct
19 Correct 287 ms 81516 KB Output is correct
20 Correct 302 ms 80408 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 47580 KB Output is correct
2 Correct 26 ms 47536 KB Output is correct
3 Correct 25 ms 47500 KB Output is correct
4 Correct 25 ms 47536 KB Output is correct
5 Correct 25 ms 47444 KB Output is correct
6 Correct 25 ms 47548 KB Output is correct
7 Correct 24 ms 47444 KB Output is correct
8 Correct 29 ms 47436 KB Output is correct
9 Correct 25 ms 47500 KB Output is correct
10 Correct 30 ms 47452 KB Output is correct
11 Correct 29 ms 47444 KB Output is correct
12 Correct 25 ms 47672 KB Output is correct
13 Correct 24 ms 47544 KB Output is correct
14 Correct 24 ms 47528 KB Output is correct
15 Correct 25 ms 47556 KB Output is correct
16 Correct 24 ms 47572 KB Output is correct
17 Correct 24 ms 47540 KB Output is correct
18 Correct 24 ms 47548 KB Output is correct
19 Correct 26 ms 47448 KB Output is correct
20 Correct 24 ms 47444 KB Output is correct
21 Correct 25 ms 47532 KB Output is correct
22 Correct 25 ms 47572 KB Output is correct
23 Correct 25 ms 47572 KB Output is correct
24 Correct 27 ms 47648 KB Output is correct
25 Correct 24 ms 47444 KB Output is correct
26 Correct 26 ms 47412 KB Output is correct
27 Correct 23 ms 47340 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 78404 KB Output is correct
2 Correct 358 ms 79076 KB Output is correct
3 Correct 342 ms 78044 KB Output is correct
4 Correct 312 ms 75624 KB Output is correct
5 Correct 296 ms 72432 KB Output is correct
6 Correct 248 ms 70988 KB Output is correct
7 Correct 248 ms 70452 KB Output is correct
8 Correct 253 ms 69432 KB Output is correct
9 Correct 220 ms 69132 KB Output is correct
10 Correct 218 ms 68732 KB Output is correct
11 Correct 200 ms 68320 KB Output is correct
12 Correct 209 ms 68076 KB Output is correct
13 Correct 198 ms 68044 KB Output is correct
14 Correct 211 ms 70716 KB Output is correct
15 Correct 394 ms 84576 KB Output is correct
16 Correct 386 ms 82480 KB Output is correct
17 Correct 337 ms 82188 KB Output is correct
18 Correct 365 ms 80152 KB Output is correct
19 Correct 317 ms 75616 KB Output is correct
20 Correct 329 ms 75660 KB Output is correct
21 Correct 306 ms 75612 KB Output is correct
22 Correct 309 ms 73548 KB Output is correct
23 Correct 258 ms 71164 KB Output is correct
24 Correct 327 ms 78376 KB Output is correct
25 Correct 349 ms 78460 KB Output is correct
26 Correct 344 ms 77076 KB Output is correct
27 Correct 332 ms 76664 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47272 KB Output is correct
2 Correct 23 ms 47316 KB Output is correct
3 Correct 23 ms 47308 KB Output is correct
4 Correct 24 ms 47188 KB Output is correct
5 Correct 23 ms 47268 KB Output is correct
6 Correct 28 ms 47188 KB Output is correct
7 Correct 24 ms 47188 KB Output is correct
8 Incorrect 23 ms 47316 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47272 KB Output is correct
2 Correct 23 ms 47316 KB Output is correct
3 Correct 23 ms 47308 KB Output is correct
4 Correct 24 ms 47188 KB Output is correct
5 Correct 23 ms 47268 KB Output is correct
6 Correct 28 ms 47188 KB Output is correct
7 Correct 24 ms 47188 KB Output is correct
8 Incorrect 23 ms 47316 KB Output isn't correct
9 Halted 0 ms 0 KB -