oj.uz

Submission #492291

# Submission time Handle Problem Language Result Execution time Memory
492291 2021-12-06T12:33:59 Z xyz Duathlon (APIO18_duathlon) C++17
66 / 100
 142 ms 29396 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 20;

vector<int> g[N], path;

int tin[N], f[N], timer;
int uin[N], uout[N], utm;
bool vis[N];
ll result;

vector<pair<int, int>> br;

int p[N], sz[N];

int root(int v){
      if(p[v] == v)
            return v;
      return p[v] = root(p[v]);
}

void merge(int a, int b){
      a = root(a);
      b = root(b);
      if(a == b)
            return;
      p[a] = b;
      sz[b] += sz[a];
}

vector<int> cg[N]; // component-graph

void dfs(int v, int p){
      vis[v] = true;
      tin[v] = f[v] = ++ timer;
      for(int x : g[v]){
            if(x == p)
                  continue;
            if(vis[x]){
                  f[v] = min(f[v], tin[x]);
            }else{
                  dfs(x, v);
                  f[v] = min(f[v], f[x]);
            }
      }
      if(p != -1){
            if(f[v] <= tin[p]) // edge (p, v) is not a bridge
                  merge(v, p);
            else
                  br.emplace_back(v, p);
      }
}

int sub[N];

int to_comp[N], ptr;
int compsz[N];

void dfs2(int v, int p, int e){
      vis[v] = true;
      uin[v] = ++ utm;
      sub[v] = sz[v];
      to_comp[v] = e;
      compsz[e] += sz[v];
      for(int x : cg[v]){
            if(x == p)
                  continue;
            dfs2(x, v, e);
            sub[v] += sub[x];
      }
      uout[v] = ++ utm;
}

bool upper(int a, int b){
      return uin[a] <= uin[b] && uout[a] >= uout[b];
}

vector<int> xyz[N];
map<int, int> mp;
void dfs3(int v, int p){
//      cout << " go " << v << endl;
      vis[v] = true;
      for(int x : cg[v]){
            if(x == p)
                  continue;
//            cout << v << " " << x <<  "  + " << 2ll * sub[x] * sz[v] * (compsz[to_comp[v]] - sub[v]) << endl;
//            cout << v << " " << x << "  + " << 1ll * sub[x] * sz[v] * (sub[v] - sub[x] - sz[v]) << endl;
            result += 2ll * sub[x] * sz[v] * (compsz[to_comp[v]] - sub[v]);
            result += 1ll * sub[x] * sz[v] * (sub[v] - sub[x] - sz[v]);
            dfs3(x, v);
      }
      mp.clear();
      for(int j : xyz[v]){
            for(int x : g[j]){
                  int h = root(x);
                  if(h != v){
                        int w = (upper(h, v) ? compsz[to_comp[v]] - sub[v] : sub[h]);
//                        cout << v << " " << j <<"  - " << 2ll * (sz[v] - 1) * mp[j] * w << endl;
                        result -= 2ll * (sz[v] - 1) * mp[j] * w;
                        mp[j] += w;
                  }
            }
      }
}


int main(){
      ios_base :: sync_with_stdio(0);
      cin.tie(0); cout.tie(0);
      int n, m;
      cin >> n >> m;
      for(int i = 0; i < m; i ++){
            int u, v;
            cin >> u >> v;
            -- u; -- v;
            g[v].push_back(u);
            g[u].push_back(v);
      }
      iota(p, p + n, 0);
      fill(sz, sz + n, 1);
      fill(vis, vis + n, false);
      for(int i = 0; i < n; i ++)
            if(!vis[i])
                  dfs(i, -1);
      for(auto [u, v] : br){
            u = root(u);
            v = root(v);
            cg[u].push_back(v);
            cg[v].push_back(u);
      }
      for(int i = 0; i < n; i ++)
            xyz[root(i)].push_back(i);
//      for(int i = 0; i < n; i ++)
//            if(p[i] == i)
//                  cout << i << " : " << sz[i] << endl;
      for(int i = 0; i < n; i ++){ // all in 1 component
            if(p[i] == i && sz[i] >= 3)
                  result += 1ll * sz[i] * (sz[i] - 1) * (sz[i] - 2);
      }
//      cout << " - " << result << endl;
      fill(vis, vis + n, false);
      for(int i = 0; i < n; i ++)
            if(!vis[root(i)])
                  dfs2(root(i), -1, ptr ++);
      for(int i = 0; i < n; i ++){ // 2 and 1 in different components
            if(p[i] == i && sz[i] >= 2){
                  for(int j : xyz[i]){
                        int trash = 0;
                        for(int x : g[j]){
                              int h = root(x);
                              if(h != i){
                                    trash += (upper(h, i) ? compsz[to_comp[i]] - sub[i] : sub[h]);
                              }
                        }
                        result += 2ll * (sz[i] - 1) * (compsz[to_comp[i]] - sz[i] - trash);
                  }
            }
      }
//      cout << " - " << result << endl;
      fill(vis, vis + n, false);
      for(int i = 0; i < n; i ++)
            if(!vis[root(i)])
                  dfs3(root(i), -1);
      cout << result;

}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 20604 KB Output is correct
2 Correct 57 ms 20544 KB Output is correct
3 Correct 98 ms 23832 KB Output is correct
4 Correct 79 ms 21532 KB Output is correct
5 Correct 88 ms 20628 KB Output is correct
6 Correct 107 ms 23132 KB Output is correct
7 Correct 106 ms 21072 KB Output is correct
8 Correct 110 ms 21560 KB Output is correct
9 Correct 117 ms 19684 KB Output is correct
10 Correct 102 ms 19516 KB Output is correct
11 Correct 95 ms 17744 KB Output is correct
12 Correct 95 ms 17732 KB Output is correct
13 Correct 89 ms 17980 KB Output is correct
14 Correct 106 ms 17700 KB Output is correct
15 Correct 66 ms 18004 KB Output is correct
16 Correct 66 ms 17636 KB Output is correct
17 Correct 12 ms 14028 KB Output is correct
18 Correct 13 ms 14080 KB Output is correct
19 Correct 13 ms 14028 KB Output is correct
20 Correct 13 ms 14092 KB Output is correct
21 Correct 12 ms 14028 KB Output is correct
22 Correct 13 ms 14028 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 20912 KB Output is correct
2 Correct 139 ms 20996 KB Output is correct
3 Correct 119 ms 20920 KB Output is correct
4 Correct 118 ms 20920 KB Output is correct
5 Correct 115 ms 20960 KB Output is correct
6 Correct 142 ms 29396 KB Output is correct
7 Correct 129 ms 26404 KB Output is correct
8 Correct 129 ms 24900 KB Output is correct
9 Correct 131 ms 23580 KB Output is correct
10 Correct 122 ms 20920 KB Output is correct
11 Correct 116 ms 20896 KB Output is correct
12 Correct 115 ms 20932 KB Output is correct
13 Correct 120 ms 20920 KB Output is correct
14 Correct 109 ms 20664 KB Output is correct
15 Correct 117 ms 20604 KB Output is correct
16 Correct 68 ms 18892 KB Output is correct
17 Correct 88 ms 21512 KB Output is correct
18 Correct 86 ms 21500 KB Output is correct
19 Correct 87 ms 21512 KB Output is correct
20 Correct 94 ms 21552 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7472 KB Output is correct
2 Correct 4 ms 7500 KB Output is correct
3 Correct 5 ms 7500 KB Output is correct
4 Correct 4 ms 7500 KB Output is correct
5 Correct 4 ms 7500 KB Output is correct
6 Correct 4 ms 7500 KB Output is correct
7 Correct 4 ms 7500 KB Output is correct
8 Correct 4 ms 7500 KB Output is correct
9 Correct 4 ms 7500 KB Output is correct
10 Correct 4 ms 7500 KB Output is correct
11 Correct 4 ms 7500 KB Output is correct
12 Correct 5 ms 7500 KB Output is correct
13 Correct 5 ms 7516 KB Output is correct
14 Correct 5 ms 7500 KB Output is correct
15 Correct 5 ms 7500 KB Output is correct
16 Correct 5 ms 7516 KB Output is correct
17 Correct 4 ms 7500 KB Output is correct
18 Correct 4 ms 7500 KB Output is correct
19 Correct 4 ms 7500 KB Output is correct
20 Correct 4 ms 7500 KB Output is correct
21 Correct 6 ms 7500 KB Output is correct
22 Correct 4 ms 7500 KB Output is correct
23 Correct 4 ms 7500 KB Output is correct
24 Correct 4 ms 7500 KB Output is correct
25 Correct 3 ms 7500 KB Output is correct
26 Correct 4 ms 7372 KB Output is correct
27 Correct 4 ms 7372 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 20924 KB Output is correct
2 Correct 136 ms 20796 KB Output is correct
3 Correct 136 ms 18412 KB Output is correct
4 Correct 117 ms 18112 KB Output is correct
5 Correct 109 ms 16964 KB Output is correct
6 Correct 90 ms 16472 KB Output is correct
7 Correct 83 ms 16320 KB Output is correct
8 Correct 83 ms 16068 KB Output is correct
9 Correct 82 ms 15960 KB Output is correct
10 Correct 77 ms 15936 KB Output is correct
11 Correct 70 ms 15868 KB Output is correct
12 Correct 64 ms 15868 KB Output is correct
13 Correct 65 ms 15632 KB Output is correct
14 Correct 64 ms 16276 KB Output is correct
15 Correct 142 ms 24876 KB Output is correct
16 Correct 140 ms 23120 KB Output is correct
17 Correct 133 ms 22504 KB Output is correct
18 Correct 132 ms 21192 KB Output is correct
19 Correct 123 ms 18140 KB Output is correct
20 Correct 128 ms 18136 KB Output is correct
21 Correct 122 ms 18112 KB Output is correct
22 Correct 111 ms 17820 KB Output is correct
23 Correct 88 ms 17356 KB Output is correct
24 Correct 122 ms 20264 KB Output is correct
25 Correct 120 ms 20324 KB Output is correct
26 Correct 108 ms 19004 KB Output is correct
27 Correct 110 ms 19064 KB Output is correct

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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