oj.uz

Submission #734868

# Submission time Handle Problem Language Result Execution time Memory
734868 2023-05-03T07:38:42 Z keisuke6 Duathlon (APIO18_duathlon) C++14
23 / 100
 157 ms 14392 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
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 N,M;
vector<vector<int>> G(100100);
vector<int> A(100100,0);
void f(int u, int p){
  if(A[u]) return;
  A[u] = 1;
  for(int x:G[u]){
    if(x == p) continue;
    f(x,u);
    A[u] += A[x];
  }
  return;
}
signed main(){
  cin>>N>>M;
  Unionfind uf(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);
    uf.unite(a,b);
  }
  for(int i=0;i<N;i++) f(i,-1);
  int ans = 0;
  for(int i=0;i<N;i++){
    int n = uf.size(i);
    vector<int> S = {n-A[i]};
    for(int x:G[i]){
      if(A[x] > A[i]) continue;
      S.push_back(A[x]);
    }
    int sum = 0;
    int dec = 0;
    for(int x:S){
      sum += x;
      dec += x*x;
    }
    ans += sum*sum-dec;
  }
  cout<<ans<<endl;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3412 KB Output is correct
2 Correct 3 ms 3412 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 3 ms 3456 KB Output is correct
5 Correct 3 ms 3540 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3456 KB Output is correct
8 Correct 3 ms 3412 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Correct 3 ms 3452 KB Output is correct
11 Correct 3 ms 3456 KB Output is correct
12 Correct 3 ms 3412 KB Output is correct
13 Correct 3 ms 3412 KB Output is correct
14 Correct 3 ms 3412 KB Output is correct
15 Correct 3 ms 3456 KB Output is correct
16 Correct 3 ms 3456 KB Output is correct
17 Correct 3 ms 3460 KB Output is correct
18 Correct 3 ms 3412 KB Output is correct
19 Correct 3 ms 3412 KB Output is correct
20 Correct 3 ms 3416 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 8712 KB Output is correct
2 Correct 111 ms 9924 KB Output is correct
3 Correct 123 ms 9968 KB Output is correct
4 Correct 94 ms 9940 KB Output is correct
5 Correct 102 ms 9980 KB Output is correct
6 Correct 157 ms 12680 KB Output is correct
7 Correct 106 ms 12184 KB Output is correct
8 Correct 101 ms 11588 KB Output is correct
9 Correct 105 ms 11004 KB Output is correct
10 Correct 100 ms 9992 KB Output is correct
11 Correct 106 ms 9932 KB Output is correct
12 Correct 97 ms 10024 KB Output is correct
13 Correct 95 ms 9984 KB Output is correct
14 Correct 102 ms 9548 KB Output is correct
15 Correct 82 ms 9176 KB Output is correct
16 Correct 54 ms 7980 KB Output is correct
17 Correct 74 ms 11712 KB Output is correct
18 Correct 78 ms 11012 KB Output is correct
19 Correct 85 ms 10928 KB Output is correct
20 Correct 73 ms 10580 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 8716 KB Output is correct
2 Correct 117 ms 9872 KB Output is correct
3 Incorrect 125 ms 10532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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