oj.uz

Submission #734862

# Submission time Handle Problem Language Result Execution time Memory
734862 2023-05-03T07:28:36 Z keisuke6 Duathlon (APIO18_duathlon) C++14
8 / 100
 128 ms 12832 KB 
#include <bits/stdc++.h>
using namespace std;
bool sub3(vector<vector<int>> &G){
  for(int i=0;i<G.size();i++)if(G[i].size() > 2) return false;
  return true;
}
struct Unionfind{
  vector<int> par, siz;
  //初期化
  Unionfind(int n) : par(n,-1) , siz(n,1) {}
  int root(int x) {
    if(par[x] == -1) return x;
    else return par[x] = root(par[x]);
  }
  bool issame(int x,int y) {
    return root(x) == root(y);
  }
  bool unite(int x, int y){
    x = root(x); y = root(y);
    if(x ==  y) return false;
    if(siz[x] < siz[y]) swap(x,y);
    par[y] =  x;
    siz[x] += siz[y];
    return  true;
  }
  int size(int x) {
    return siz[root(x)];
  }
};
int main(){
  int N,M;
  cin>>N>>M;
  vector<vector<int>> G(N);
  for(int i=0;i<M;i++){
    int a,b;
    cin>>a>>b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  if(sub3(G)){
    Unionfind uf(N);
    for(int i=0;i<N;i++){
      for(int x:G[i]) uf.unite(i,x);
    }
    map<int,int> mm;
    for(int i=0;i<N;i++)for(int x:G[i]) mm[uf.root(x)]++;
    map<int,int> m;
    for(int i=0;i<N;i++) m[uf.root(i)]++;
    long long ans = 0;
    for(auto x:m){
      long long n = x.second;
      if(mm[x.first]/2 == n) ans += n*(n-1)*(n-2);
      else for(long long i=2;i<n;i++) ans += (i-1)*(n-i)*2;
    }
    cout<<ans<<endl;
    return 0;
  }
}

Compilation message

count_triplets.cpp: In function 'bool sub3(std::vector<std::vector<int> >&)':
count_triplets.cpp:4:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 |   for(int i=0;i<G.size();i++)if(G[i].size() > 2) return false;
      |               ~^~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 6436 KB Output is correct
2 Correct 93 ms 7732 KB Output is correct
3 Correct 100 ms 7724 KB Output is correct
4 Correct 86 ms 7720 KB Output is correct
5 Correct 92 ms 7756 KB Output is correct
6 Correct 91 ms 7784 KB Output is correct
7 Correct 92 ms 7756 KB Output is correct
8 Correct 88 ms 7720 KB Output is correct
9 Correct 94 ms 7696 KB Output is correct
10 Correct 90 ms 7756 KB Output is correct
11 Correct 114 ms 9832 KB Output is correct
12 Correct 128 ms 9816 KB Output is correct
13 Correct 113 ms 10508 KB Output is correct
14 Correct 104 ms 10264 KB Output is correct
15 Correct 85 ms 11364 KB Output is correct
16 Correct 81 ms 11208 KB Output is correct
17 Correct 36 ms 12832 KB Output is correct
18 Correct 38 ms 12752 KB Output is correct
19 Correct 33 ms 12808 KB Output is correct
20 Correct 42 ms 12808 KB Output is correct
21 Correct 38 ms 12748 KB Output is correct
22 Correct 37 ms 12804 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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