oj.uz

Submission #734337

# Submission time Handle Problem Language Result Execution time Memory
734337 2023-05-02T09:46:07 Z cig32 Duathlon (APIO18_duathlon) C++17
0 / 100
 142 ms 45200 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 bruh;
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(bruh - ret);
  int con = (node <= n ? 2 * (bruh-1) : 0);
  int ps = 0;
  for(int x: vt) {
    con += ps * x * 2;
    ps += x;
  }
  ans += con * w[node];
  return ret;
}
void count(int node, int prv) {
  vis[node] = 1;
  bruh += (node <= n);
  for(int x: rst[node]) if(x != prv) count(x, node);
}
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;
  for(int i=1; i<=n; i++) {
    if(!vis[i]) {
      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();
  for(int i=1; i<=n+m; i++) vis[i] = 0;
  for(int i=1; i<=n+m; i++) {
    if(!vis[i]) {
      bruh = 0;
      count(i, -1);
      calc(i, -1);
    }
  }
  cout << ans << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19060 KB Output is correct
3 Correct 10 ms 19112 KB Output is correct
4 Correct 11 ms 19028 KB Output is correct
5 Correct 11 ms 19080 KB Output is correct
6 Correct 11 ms 19128 KB Output is correct
7 Correct 12 ms 19028 KB Output is correct
8 Correct 10 ms 19072 KB Output is correct
9 Correct 11 ms 19064 KB Output is correct
10 Correct 10 ms 19028 KB Output is correct
11 Correct 11 ms 19028 KB Output is correct
12 Correct 12 ms 19028 KB Output is correct
13 Correct 10 ms 19028 KB Output is correct
14 Correct 11 ms 19124 KB Output is correct
15 Correct 11 ms 19124 KB Output is correct
16 Correct 11 ms 19156 KB Output is correct
17 Correct 10 ms 19028 KB Output is correct
18 Correct 11 ms 19044 KB Output is correct
19 Incorrect 11 ms 19028 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19060 KB Output is correct
3 Correct 10 ms 19112 KB Output is correct
4 Correct 11 ms 19028 KB Output is correct
5 Correct 11 ms 19080 KB Output is correct
6 Correct 11 ms 19128 KB Output is correct
7 Correct 12 ms 19028 KB Output is correct
8 Correct 10 ms 19072 KB Output is correct
9 Correct 11 ms 19064 KB Output is correct
10 Correct 10 ms 19028 KB Output is correct
11 Correct 11 ms 19028 KB Output is correct
12 Correct 12 ms 19028 KB Output is correct
13 Correct 10 ms 19028 KB Output is correct
14 Correct 11 ms 19124 KB Output is correct
15 Correct 11 ms 19124 KB Output is correct
16 Correct 11 ms 19156 KB Output is correct
17 Correct 10 ms 19028 KB Output is correct
18 Correct 11 ms 19044 KB Output is correct
19 Incorrect 11 ms 19028 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 41768 KB Output is correct
2 Correct 82 ms 41828 KB Output is correct
3 Incorrect 65 ms 33940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19284 KB Output is correct
2 Correct 11 ms 19180 KB Output is correct
3 Correct 12 ms 19196 KB Output is correct
4 Correct 11 ms 19416 KB Output is correct
5 Correct 11 ms 19284 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 19364 KB Output is correct
9 Correct 11 ms 19284 KB Output is correct
10 Incorrect 10 ms 19148 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 34452 KB Output is correct
2 Correct 110 ms 34608 KB Output is correct
3 Correct 124 ms 34436 KB Output is correct
4 Correct 119 ms 34560 KB Output is correct
5 Correct 110 ms 34416 KB Output is correct
6 Correct 124 ms 45200 KB Output is correct
7 Correct 141 ms 42148 KB Output is correct
8 Correct 126 ms 40116 KB Output is correct
9 Correct 124 ms 38160 KB Output is correct
10 Incorrect 88 ms 31088 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 19284 KB Output is correct
2 Correct 12 ms 19196 KB Output is correct
3 Correct 14 ms 19284 KB Output is correct
4 Correct 12 ms 19156 KB Output is correct
5 Correct 12 ms 19260 KB Output is correct
6 Correct 11 ms 19224 KB Output is correct
7 Correct 11 ms 19160 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 19156 KB Output is correct
11 Correct 10 ms 19272 KB Output is correct
12 Correct 11 ms 19284 KB Output is correct
13 Correct 11 ms 19284 KB Output is correct
14 Correct 12 ms 19284 KB Output is correct
15 Correct 12 ms 19284 KB Output is correct
16 Incorrect 12 ms 19252 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 34440 KB Output is correct
2 Correct 119 ms 34192 KB Output is correct
3 Correct 115 ms 33740 KB Output is correct
4 Correct 120 ms 32732 KB Output is correct
5 Correct 122 ms 31420 KB Output is correct
6 Correct 108 ms 30796 KB Output is correct
7 Correct 106 ms 30760 KB Output is correct
8 Correct 97 ms 30236 KB Output is correct
9 Correct 97 ms 30236 KB Output is correct
10 Correct 85 ms 30028 KB Output is correct
11 Correct 82 ms 29952 KB Output is correct
12 Correct 92 ms 29996 KB Output is correct
13 Correct 96 ms 30088 KB Output is correct
14 Correct 108 ms 32748 KB Output is correct
15 Correct 138 ms 41956 KB Output is correct
16 Correct 142 ms 39432 KB Output is correct
17 Correct 136 ms 40216 KB Output is correct
18 Correct 130 ms 37836 KB Output is correct
19 Incorrect 110 ms 32336 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19060 KB Output is correct
3 Correct 10 ms 19112 KB Output is correct
4 Correct 11 ms 19028 KB Output is correct
5 Correct 11 ms 19080 KB Output is correct
6 Correct 11 ms 19128 KB Output is correct
7 Correct 12 ms 19028 KB Output is correct
8 Correct 10 ms 19072 KB Output is correct
9 Correct 11 ms 19064 KB Output is correct
10 Correct 10 ms 19028 KB Output is correct
11 Correct 11 ms 19028 KB Output is correct
12 Correct 12 ms 19028 KB Output is correct
13 Correct 10 ms 19028 KB Output is correct
14 Correct 11 ms 19124 KB Output is correct
15 Correct 11 ms 19124 KB Output is correct
16 Correct 11 ms 19156 KB Output is correct
17 Correct 10 ms 19028 KB Output is correct
18 Correct 11 ms 19044 KB Output is correct
19 Incorrect 11 ms 19028 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 11 ms 19060 KB Output is correct
3 Correct 10 ms 19112 KB Output is correct
4 Correct 11 ms 19028 KB Output is correct
5 Correct 11 ms 19080 KB Output is correct
6 Correct 11 ms 19128 KB Output is correct
7 Correct 12 ms 19028 KB Output is correct
8 Correct 10 ms 19072 KB Output is correct
9 Correct 11 ms 19064 KB Output is correct
10 Correct 10 ms 19028 KB Output is correct
11 Correct 11 ms 19028 KB Output is correct
12 Correct 12 ms 19028 KB Output is correct
13 Correct 10 ms 19028 KB Output is correct
14 Correct 11 ms 19124 KB Output is correct
15 Correct 11 ms 19124 KB Output is correct
16 Correct 11 ms 19156 KB Output is correct
17 Correct 10 ms 19028 KB Output is correct
18 Correct 11 ms 19044 KB Output is correct
19 Incorrect 11 ms 19028 KB Output isn't correct
20 Halted 0 ms 0 KB -