oj.uz

Submission #829906

# Submission time Handle Problem Language Result Execution time Memory
829906 2023-08-18T15:44:25 Z tolbi Duathlon (APIO18_duathlon) C++17
31 / 100
 165 ms 35004 KB 
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define tol(bi) (1LL<<((int)(bi)))
#define endl '\n'
typedef long long ll;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
ll solve(int n, vector<int> u, vector<int> v){
    int totn = n;
    vector<vector<int>> arr(n);
    for (int i = 0; i < u.size(); i++){
        arr[u[i]].push_back(v[i]);
        arr[v[i]].push_back(u[i]);
    }
    vector<int> dept(n,-1);
    vector<int> ele(n);
    vector<int> sz;
    vector<vector<int>> stk(n);
    vector<vector<int>> hehe;
    function<int(int,int)> f;
    vector<int> par(n);
    f = [&](int node, int lnode)->int{
        if (lnode!=-1) par[node]=lnode;
        int mide = dept[node];
        stk[node].push_back(node);
        for (int i = 0; i < arr[node].size(); i++){
            if (arr[node][i]==lnode) continue;
            if (dept[arr[node][i]]!=-1){
                mide=min(mide,dept[arr[node][i]]);
                continue;
            }
            dept[arr[node][i]]=dept[node]+1;
            mide=min(mide,f(arr[node][i],node));
            if (stk[node].size()<stk[arr[node][i]].size()) swap(stk[node],stk[arr[node][i]]);
            while (stk[arr[node][i]].size()){
                stk[node].push_back(stk[arr[node][i]].back());
                stk[arr[node][i]].pop_back();
            }
        }
        if (mide>=dept[node]){
            sz.push_back(0);
            while (stk[node].size()){
                ele[stk[node].back()]=hehe.size();
                stk[node].pop_back();
                sz.back()++;
            }
            hehe.push_back(vector<int>());
        }
        return mide;
    };
    dept[0]=0;
    f(0,-1);
    for (int i = 1; i < n; i++){
        if (ele[i]!=ele[par[i]]){
            hehe[ele[i]].push_back(ele[par[i]]);
            hehe[ele[par[i]]].push_back(ele[i]);
        }
    }
    n=hehe.size();
    dept[0]=0;
    swap(arr,hehe);
    ll ans = 0;
    for (int i = 0; i < sz.size(); i++){
        ans+=(ll)sz[i]*((ll)sz[i]-1)*((ll)sz[i]-2);
    }//3 from cycle
    vector<int> subsz(n);
    //coutarr(sz);
    f = [&](int node, int lnode)->int{
        subsz[node]=sz[node];
        for (int i = 0; i < arr[node].size(); i++){
            if (arr[node][i]==lnode) continue;
            f(arr[node][i],node);
            subsz[node]+=subsz[arr[node][i]];
            ans+=((ll)subsz[arr[node][i]])*((ll)sz[node])*((ll)totn-subsz[arr[node][i]]-sz[node]);
            //2 from outside, 1 from cycle
            ans+=(ll)(sz[node]-1)*((ll)sz[node]-1)*(ll)subsz[arr[node][i]]*2LL;
            //2 from cycle, 1 from outside
        }
        ans+=(ll)(sz[node]-1)*((ll)sz[node]-1)*((ll)totn-subsz[node])*2LL;
        ans+=(ll)(sz[node])*((ll)totn-subsz[node])*((ll)subsz[node]-(ll)sz[node]);
        return 23;
    };
    f(0,-1);
    return ans;
}
int32_t main(){
    int T = 1;
    int tno = 0;
    while (T-(tno++)){
        deci(n);deci(m);
        vector<int> par(n);
        iota(par.begin(), par.end(), 0);
        function<int(int)> find;
        find = [&](int node)->int{
            if (par[node]==node) return node;
            return par[node]=find(par[node]);
        };
        vector<pair<int,int>> edges(m);
        for (int i = 0; i < m; i++){
            cin>>edges[i].first>>edges[i].second;
            edges[i].first--,edges[i].second--;
            int u = edges[i].first;
            int v = edges[i].second;
            u=find(u);
            v=find(v);
            if (ayahya()%2) swap(u,v);
            par[u]=v;
        }
        map<int,int> mp;
        map<int,vector<int>> u;
        map<int,vector<int>> v;
        vector<int> indis(n);
        for (int i = 0; i < n; i++){
            indis[i]=mp[find(i)]++;
        }
        for (int i = 0; i < m; i++){
            u[find(edges[i].first)].push_back(indis[edges[i].first]);
            v[find(edges[i].first)].push_back(indis[edges[i].second]);
        }
        ll ans = 0;
        for (auto it : mp){
            ans+=solve(it.second,u[it.first],v[it.first]);
            u.erase(it.first);
            v.erase(it.first);
        }
        cout<<ans<<endl;
    }
}

Compilation message

count_triplets.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
count_triplets.cpp: In function 'll solve(int, std::vector<int>, std::vector<int>)':
count_triplets.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i < u.size(); i++){
      |                     ~~^~~~~~~~~~
count_triplets.cpp: In lambda function:
count_triplets.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int i = 0; i < arr[node].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~
count_triplets.cpp: In function 'll solve(int, std::vector<int>, std::vector<int>)':
count_triplets.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i = 0; i < sz.size(); i++){
      |                     ~~^~~~~~~~~~~
count_triplets.cpp: In lambda function:
count_triplets.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i = 0; i < arr[node].size(); i++){
      |                         ~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 35004 KB Output is correct
2 Correct 122 ms 35004 KB Output is correct
3 Correct 97 ms 19948 KB Output is correct
4 Correct 124 ms 26924 KB Output is correct
5 Correct 93 ms 15164 KB Output is correct
6 Correct 96 ms 19248 KB Output is correct
7 Correct 83 ms 10236 KB Output is correct
8 Correct 101 ms 14780 KB Output is correct
9 Correct 88 ms 6556 KB Output is correct
10 Correct 82 ms 9192 KB Output is correct
11 Correct 153 ms 8408 KB Output is correct
12 Correct 129 ms 7900 KB Output is correct
13 Correct 131 ms 9656 KB Output is correct
14 Correct 117 ms 8908 KB Output is correct
15 Correct 106 ms 10740 KB Output is correct
16 Correct 112 ms 10148 KB Output is correct
17 Correct 49 ms 5800 KB Output is correct
18 Correct 55 ms 5808 KB Output is correct
19 Correct 70 ms 5716 KB Output is correct
20 Correct 59 ms 5756 KB Output is correct
21 Correct 50 ms 5812 KB Output is correct
22 Correct 50 ms 5796 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 22052 KB Output is correct
2 Correct 108 ms 22064 KB Output is correct
3 Correct 101 ms 22068 KB Output is correct
4 Correct 106 ms 21964 KB Output is correct
5 Correct 101 ms 21940 KB Output is correct
6 Correct 127 ms 32764 KB Output is correct
7 Correct 165 ms 28576 KB Output is correct
8 Correct 124 ms 26936 KB Output is correct
9 Correct 111 ms 25220 KB Output is correct
10 Correct 90 ms 13260 KB Output is correct
11 Correct 97 ms 19564 KB Output is correct
12 Correct 91 ms 8660 KB Output is correct
13 Correct 86 ms 7164 KB Output is correct
14 Correct 105 ms 5116 KB Output is correct
15 Correct 104 ms 6692 KB Output is correct
16 Correct 100 ms 9372 KB Output is correct
17 Correct 97 ms 24028 KB Output is correct
18 Correct 112 ms 23220 KB Output is correct
19 Correct 86 ms 23596 KB Output is correct
20 Correct 88 ms 22948 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Incorrect 1 ms 468 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 22072 KB Output is correct
2 Correct 102 ms 21936 KB Output is correct
3 Incorrect 105 ms 20144 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -