oj.uz

Submission #744558

# Submission time Handle Problem Language Result Execution time Memory
744558 2023-05-18T18:14:10 Z Abito Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048576 KB 
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define ep insert
#define pow pwr
#define sqrt sqrtt
#define elif else if
#define y1 YONE
#define int long long
#define ppb pop_back
using namespace std;
const int N=1e6+5;
int n,m,sz[N],par[N],dpar[N],dsz[N];
vector<int> adj[N],q;
set<int> s[N];
bool vis[N];
int getpar(int x){
    if (x==dpar[x]) return x;
    return dpar[x]=getpar(dpar[x]);
}
void link(int x,int y){
    x=getpar(x);y=getpar(y);
    if (x==y) return;
    if (dsz[x]>dsz[y]) swap(x,y);
    dpar[x]=y;
    dsz[y]+=dsz[x];
    return;
}
int getsize(int node,int p){
    par[node]=p;
    sz[node]=1;
    for (auto u:adj[node]){
        if (u==p) continue;
        sz[node]+=getsize(u,node);
    }return sz[node];
}
void bfs(int node){
    q.clear();
    q.pb(node);
    par[node]=node;
    for (int i=0;i<q.size();i++){
        int node=q[i];
        for (auto u:adj[node]){
            if (par[u]) continue;
            q.pb(u);
            par[u]=node;
        }
    }return;
}
int32_t main(){
    //ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>m;
    if (n<=11){
        for (int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            adj[x].pb(y);
            adj[y].pb(x);
        }
        int ans=0;
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                par[j]=0;
                s[j].clear();
                s[j].ep(j);
            }
            bfs(i);
            reverse(q.begin(),q.end());
            for (int i=0;i<q.size();i++){
                for (auto u:s[q[i]]) s[par[q[i]]].ep(u);
            }
            for (auto x:adj[i]){
                for (auto y:adj[i]){
                    int f=s[x].size(),g=s[y].size();
                    if (s[x].size()<s[y].size()){
                        for (auto d:s[x]){
                            if (s[y].count(d)) {f--;g--;}
                        }
                    }
                    else{
                        for (auto d:s[y]){
                            if (s[x].count(d)) {f--;g--;}
                        }
                    }ans+=f*g;
                }
            }
        }cout<<ans<<endl;
        return 0;
    }
    for (int i=1;i<=n;i++){
        dsz[i]=1;
        dpar[i]=i;
    }
    for (int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
        link(x,y);
    }
    for (int i=1;i<=n;i++){
        if (sz[i]) continue;
        getsize(i,0);
    }
    int ans=0;
    for (int i=1;i<=n;i++){
        int x=sz[i]-1;
        for (auto u:adj[i]){
            if (u==par[i]) continue;
            x-=sz[u];
            ans+=x*sz[u];
        }ans+=(dsz[getpar(i)]-sz[i])*(sz[i]-1);
    }
    cout<<ans*2LL<<endl;
    return 0;
}

Compilation message

count_triplets.cpp: In function 'void bfs(long long int)':
count_triplets.cpp:43:19: 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]
   43 |     for (int i=0;i<q.size();i++){
      |                  ~^~~~~~~~~
count_triplets.cpp: In function 'int32_t main()':
count_triplets.cpp:71:27: 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]
   71 |             for (int i=0;i<q.size();i++){
      |                          ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 70740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 70740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 380872 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70740 KB Output is correct
2 Correct 35 ms 70788 KB Output is correct
3 Correct 39 ms 70760 KB Output is correct
4 Correct 33 ms 70764 KB Output is correct
5 Correct 38 ms 70868 KB Output is correct
6 Correct 33 ms 70824 KB Output is correct
7 Correct 33 ms 70792 KB Output is correct
8 Correct 33 ms 70736 KB Output is correct
9 Correct 34 ms 70792 KB Output is correct
10 Correct 38 ms 70804 KB Output is correct
11 Correct 34 ms 70772 KB Output is correct
12 Correct 36 ms 70844 KB Output is correct
13 Correct 33 ms 70784 KB Output is correct
14 Correct 35 ms 70760 KB Output is correct
15 Correct 32 ms 70756 KB Output is correct
16 Correct 35 ms 70740 KB Output is correct
17 Correct 32 ms 70744 KB Output is correct
18 Correct 33 ms 70752 KB Output is correct
19 Correct 37 ms 70764 KB Output is correct
20 Correct 34 ms 70756 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 78800 KB Output is correct
2 Correct 139 ms 78784 KB Output is correct
3 Correct 124 ms 78968 KB Output is correct
4 Correct 123 ms 78772 KB Output is correct
5 Correct 141 ms 79120 KB Output is correct
6 Correct 133 ms 80832 KB Output is correct
7 Correct 138 ms 80600 KB Output is correct
8 Correct 130 ms 79980 KB Output is correct
9 Correct 136 ms 79564 KB Output is correct
10 Correct 131 ms 78892 KB Output is correct
11 Correct 120 ms 78856 KB Output is correct
12 Correct 121 ms 78800 KB Output is correct
13 Correct 122 ms 78800 KB Output is correct
14 Correct 141 ms 78556 KB Output is correct
15 Correct 106 ms 78184 KB Output is correct
16 Correct 77 ms 76892 KB Output is correct
17 Correct 107 ms 79000 KB Output is correct
18 Correct 107 ms 79004 KB Output is correct
19 Correct 111 ms 78984 KB Output is correct
20 Correct 110 ms 78972 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70844 KB Output is correct
2 Correct 37 ms 70840 KB Output is correct
3 Runtime error 670 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 78836 KB Output is correct
2 Correct 130 ms 78568 KB Output is correct
3 Runtime error 807 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 70740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 70740 KB Output isn't correct
2 Halted 0 ms 0 KB -