oj.uz

Submission #59983

# Submission time Handle Problem Language Result Execution time Memory
59983 2018-07-23T11:55:10 Z Flugan42 Duathlon (APIO18_duathlon) C++14
31 / 100
 299 ms 12320 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);
  }
  bool check = true;
  rep(i,0,n) if (sz(edges[i])>2) check = false;
  vis.assign(n,0); vis2.assign(n,0); cnt.assign(n,-1);
  cur = 1; ll res = 0;
  if (check){
    rep(i,0,n){
      if (vis[i] != 0) continue;
      tree.clear();
      vis[i] = cur; dfs(i); cur++;
      bool cyc = true; ll A = sz(tree);
      rep(j,0,A) if (sz(edges[tree[j]]) < 2) cyc = false;
      if (cyc) res += A*(A-1)*(A-2);
      else res += A*(A-1)*(A-2)/3;
    }
    cout << res << endl;
    exit(0);
  }
  rep(i,0,n){
    if (vis[i] != 0) continue;
    tree.clear();
    vis[i] = cur; dfs(i); cur++;
    dfs2(tree[0]);
    rep(j,0,sz(tree)){ res += center(tree[j]);  }
  }
  cout << res << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 248 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 248 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 235 ms 12320 KB Output is correct
2 Correct 208 ms 12320 KB Output is correct
3 Correct 222 ms 12320 KB Output is correct
4 Correct 239 ms 12320 KB Output is correct
5 Correct 228 ms 12320 KB Output is correct
6 Correct 207 ms 12320 KB Output is correct
7 Correct 234 ms 12320 KB Output is correct
8 Correct 197 ms 12320 KB Output is correct
9 Correct 192 ms 12320 KB Output is correct
10 Correct 206 ms 12320 KB Output is correct
11 Correct 187 ms 12320 KB Output is correct
12 Correct 174 ms 12320 KB Output is correct
13 Correct 156 ms 12320 KB Output is correct
14 Correct 166 ms 12320 KB Output is correct
15 Correct 118 ms 12320 KB Output is correct
16 Correct 95 ms 12320 KB Output is correct
17 Correct 11 ms 12320 KB Output is correct
18 Correct 9 ms 12320 KB Output is correct
19 Correct 10 ms 12320 KB Output is correct
20 Correct 9 ms 12320 KB Output is correct
21 Correct 9 ms 12320 KB Output is correct
22 Correct 10 ms 12320 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 12320 KB Output is correct
2 Correct 190 ms 12320 KB Output is correct
3 Correct 284 ms 12320 KB Output is correct
4 Correct 254 ms 12320 KB Output is correct
5 Correct 193 ms 12320 KB Output is correct
6 Correct 184 ms 12320 KB Output is correct
7 Correct 299 ms 12320 KB Output is correct
8 Correct 259 ms 12320 KB Output is correct
9 Correct 230 ms 12320 KB Output is correct
10 Correct 283 ms 12320 KB Output is correct
11 Correct 216 ms 12320 KB Output is correct
12 Correct 221 ms 12320 KB Output is correct
13 Correct 195 ms 12320 KB Output is correct
14 Correct 237 ms 12320 KB Output is correct
15 Correct 183 ms 12320 KB Output is correct
16 Correct 134 ms 12320 KB Output is correct
17 Correct 213 ms 12320 KB Output is correct
18 Correct 140 ms 12320 KB Output is correct
19 Correct 149 ms 12320 KB Output is correct
20 Correct 169 ms 12320 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 12320 KB Output is correct
2 Correct 227 ms 12320 KB Output is correct
3 Incorrect 264 ms 12320 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 248 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 248 KB Output isn't correct
2 Halted 0 ms 0 KB -