oj.uz

Submission #59964

# Submission time Handle Problem Language Result Execution time Memory
59964 2018-07-23T11:35:12 Z Flugan42 Duathlon (APIO18_duathlon) C++14
23 / 100
 286 ms 13968 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define inf 1000000000000000000
#define sz(x) (ll)(x).size()

ll n,m,u,v,cur;
vector<vi> edges;
vi _,vis,tree,vis2,cnt;

void dfs(ll a){
  tree.push_back(a);
  rep(i,0,sz(edges[a])){
    ll b = edges[a][i];
    if (vis[b] == 0) {
      vis[b] = cur;
      dfs(b);
    }
  }
}

ll dfs2(ll a){
  vis2[a] = 1;
  if (cnt[a] != -1) return cnt[a];
  ll ans = 1;
  rep(i,0,sz(edges[a])){
    ll b = edges[a][i];
    if (vis2[b] == 0) {
      ans += dfs2(b);
    }
  }
  return cnt[a] = ans;
}

ll center(ll a){
  ll ans = 0,big = 0;
  rep(i,0,sz(edges[a])){
    ll b = edges[a][i];
    if (cnt[b] > cnt[a]) { continue; }
    ans += (sz(tree)-1-cnt[b])*cnt[b];
    big += cnt[b];
  }
  ans += big*(sz(tree)-1-big);
  return ans;
}

int main(){
  cin >> n >> m;
  edges.assign(n,_);
  rep(i,0,m){
    cin >> u >> v; u--; v--;
    edges[u].push_back(v);
    edges[v].push_back(u);
  }
  vis.assign(n,0);
  cur = 1; ll res = 0;
  vis2.assign(n,0); cnt.assign(n,-1);
  rep(i,0,n){
    if (vis[i] != 0) continue;
    tree.clear();
    if (vis[i] == 0) { vis[i] = cur; dfs(i); cur++; }
    dfs2(tree[0]);
    rep(i,0,sz(tree)){ res += center(tree[i]);  }
  }
  cout << res << endl;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 13968 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 13968 KB Output is correct
2 Correct 3 ms 13968 KB Output is correct
3 Correct 3 ms 13968 KB Output is correct
4 Correct 4 ms 13968 KB Output is correct
5 Correct 3 ms 13968 KB Output is correct
6 Correct 4 ms 13968 KB Output is correct
7 Correct 4 ms 13968 KB Output is correct
8 Correct 4 ms 13968 KB Output is correct
9 Correct 3 ms 13968 KB Output is correct
10 Correct 3 ms 13968 KB Output is correct
11 Correct 4 ms 13968 KB Output is correct
12 Correct 4 ms 13968 KB Output is correct
13 Correct 4 ms 13968 KB Output is correct
14 Correct 3 ms 13968 KB Output is correct
15 Correct 5 ms 13968 KB Output is correct
16 Correct 5 ms 13968 KB Output is correct
17 Correct 3 ms 13968 KB Output is correct
18 Correct 5 ms 13968 KB Output is correct
19 Correct 3 ms 13968 KB Output is correct
20 Correct 3 ms 13968 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 13968 KB Output is correct
2 Correct 223 ms 13968 KB Output is correct
3 Correct 214 ms 13968 KB Output is correct
4 Correct 212 ms 13968 KB Output is correct
5 Correct 251 ms 13968 KB Output is correct
6 Correct 286 ms 13968 KB Output is correct
7 Correct 211 ms 13968 KB Output is correct
8 Correct 235 ms 13968 KB Output is correct
9 Correct 230 ms 13968 KB Output is correct
10 Correct 255 ms 13968 KB Output is correct
11 Correct 259 ms 13968 KB Output is correct
12 Correct 185 ms 13968 KB Output is correct
13 Correct 172 ms 13968 KB Output is correct
14 Correct 155 ms 13968 KB Output is correct
15 Correct 132 ms 13968 KB Output is correct
16 Correct 106 ms 13968 KB Output is correct
17 Correct 218 ms 13968 KB Output is correct
18 Correct 160 ms 13968 KB Output is correct
19 Correct 149 ms 13968 KB Output is correct
20 Correct 172 ms 13968 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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