oj.uz

Submission #734328

# Submission time Handle Problem Language Result Execution time Memory
734328 2023-05-02T09:38:09 Z cig32 Duathlon (APIO18_duathlon) C++17
0 / 100
 137 ms 45580 KB 
#include "bits/stdc++.h"
#define int long long
using namespace std;
const int MAXN = 4e5 + 10;
vector<int> adj[MAXN];
vector<int> rst[MAXN]; // round-square tree
int n, m, cur;
int tin[MAXN], low[MAXN], vis[MAXN];
stack<int> stk;
int nxt;
int ans = 0;
void dfs(int node, int prv) {
  vis[node] = 1;
  tin[node] = ++cur;
  low[node] = tin[node];
  stk.push(node);
  for(int x: adj[node]) {
    if(x != prv) {
      if(!vis[x]) {
        dfs(x, node);
        low[node] = min(low[node], low[x]);
        if(low[x] >= tin[node]) {
          while(1) {
            int u = stk.top();
            stk.pop();
            rst[u].push_back(nxt);
            rst[nxt].push_back(u);
            if(u == x) break;
          }
          rst[node].push_back(nxt);
          rst[nxt].push_back(node);
          nxt++;
        }
      }
      else {
        low[node] = min(low[node], tin[x]);
      }
    }
  }
}
int w[MAXN];
int calc(int node, int prv) {
  int ret = (node <= n);
  vector<int> vt;
  for(int x: rst[node]) {
    if(x != prv) {
      int v = calc(x, node);
      ret += v;
      vt.push_back(v);
    }
  }
  vt.push_back(n - ret);
  int con = (node <= n ? 2 * (n-1) : 0);
  int ps = 0;
  for(int x: vt) {
    con += ps * x * 2;
    ps += x;
  }
  ans += con * w[node];
  return ret;
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for(int i=1; i<=m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  nxt = n+1;
  dfs(1, -1);
  m = nxt-1 - n;
  for(int i=1; i<=n; i++) w[i] = -1;
  for(int i=n+1; i<=n+m; i++) w[i] = rst[i].size();
  calc(1, -1);
  cout << ans << '\n';
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 43072 KB Output is correct
2 Correct 85 ms 43076 KB Output is correct
3 Incorrect 62 ms 34904 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19284 KB Output is correct
2 Correct 11 ms 19260 KB Output is correct
3 Correct 12 ms 19264 KB Output is correct
4 Correct 11 ms 19412 KB Output is correct
5 Correct 12 ms 19380 KB Output is correct
6 Correct 11 ms 19284 KB Output is correct
7 Correct 11 ms 19284 KB Output is correct
8 Correct 11 ms 19264 KB Output is correct
9 Correct 11 ms 19284 KB Output is correct
10 Incorrect 12 ms 19132 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 34832 KB Output is correct
2 Correct 108 ms 34860 KB Output is correct
3 Correct 106 ms 34784 KB Output is correct
4 Correct 101 ms 34784 KB Output is correct
5 Correct 100 ms 34860 KB Output is correct
6 Correct 116 ms 45580 KB Output is correct
7 Correct 124 ms 42632 KB Output is correct
8 Correct 116 ms 40620 KB Output is correct
9 Correct 118 ms 38604 KB Output is correct
10 Incorrect 78 ms 31496 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19260 KB Output is correct
2 Correct 11 ms 19284 KB Output is correct
3 Correct 11 ms 19284 KB Output is correct
4 Correct 10 ms 19284 KB Output is correct
5 Correct 11 ms 19156 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 11 ms 19260 KB Output is correct
8 Correct 11 ms 19156 KB Output is correct
9 Correct 11 ms 19156 KB Output is correct
10 Correct 12 ms 19228 KB Output is correct
11 Correct 11 ms 19284 KB Output is correct
12 Correct 11 ms 19284 KB Output is correct
13 Correct 11 ms 19312 KB Output is correct
14 Correct 11 ms 19368 KB Output is correct
15 Correct 11 ms 19284 KB Output is correct
16 Incorrect 10 ms 19132 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 34884 KB Output is correct
2 Correct 112 ms 34780 KB Output is correct
3 Correct 126 ms 34588 KB Output is correct
4 Correct 137 ms 33708 KB Output is correct
5 Correct 109 ms 32620 KB Output is correct
6 Correct 97 ms 32076 KB Output is correct
7 Correct 93 ms 31876 KB Output is correct
8 Correct 89 ms 31424 KB Output is correct
9 Correct 89 ms 31440 KB Output is correct
10 Correct 89 ms 31396 KB Output is correct
11 Correct 84 ms 31188 KB Output is correct
12 Correct 81 ms 31160 KB Output is correct
13 Correct 82 ms 31328 KB Output is correct
14 Correct 81 ms 33932 KB Output is correct
15 Correct 122 ms 42824 KB Output is correct
16 Correct 128 ms 40144 KB Output is correct
17 Correct 126 ms 41144 KB Output is correct
18 Correct 130 ms 38800 KB Output is correct
19 Incorrect 108 ms 33296 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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