oj.uz

Submission #49505

# Submission time Handle Problem Language Result Execution time Memory
49505 2018-05-30T05:44:58 Z mirbek01 Duathlon (APIO18_duathlon) C++17
66 / 100
 702 ms 52332 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, m, used[11][N], root, vis[N];
int tin[N], fup[N], timer;
int p[N], sz[N], siz[N], P[N], SZ[N];
long long ans;
map < pair <int, int>, bool > isb, ISB;
vector <int> g[N], gr[N], vr[N], G[N];

int get(int v){
      return (p[v] == v)?v:p[v] = get(p[v]);
}
void unite(int a, int b){
      a = get(a);
      b = get(b);
      if(a != b){
            if(sz[b] > sz[a]) swap(a, b);
            p[b] = a;
            sz[a] += sz[b];
      }
}
int f_s(int v){
      return (P[v] == v)?v:P[v] = f_s(P[v]);
}
void u_s(int a, int b){
      a = f_s(a);
      b = f_s(b);
      if(a != b){
            if(SZ[a] > SZ[b]) swap(a, b);
            P[b] = a;
            SZ[a] += SZ[b];
      }
}

void dfs(int v, int pr = 0){
      used[0][v] = 1;
      tin[v] = fup[v] = ++ timer;
      for(int to : g[v]){
            if(to == pr) continue;
            if(used[0][to])
                  fup[v] = min(fup[v], tin[to]);
            else {
                  dfs(to, v);
                  fup[v] = min(fup[v], fup[to]);
                  if(fup[to] > tin[v]){
                        isb[{v, to}] = 1;
                        isb[{to, v}] = 1;
                  }
            }
      }
}


void dfs1(int v){
      used[1][v] = 1;
      for(int to : g[v]){
            if(used[1][to]) continue;
            if(!isb[{v, to}])
                  unite(v, to);
            dfs1(to);
      }
}

void dfs2(int v){
      used[2][v] = 1;
      vr[get(v)].push_back(v);
      for(int to : g[v]){
            if(used[2][to]) continue;
            if(get(v) != get(to)){
                  gr[get(v)].push_back(get(to));
                  gr[get(to)].push_back(get(v));
            }
            dfs2(to);
      }
}

void dfs3(int v){
      used[3][v] = 1;
      siz[v] = sz[v];
      for(int to : gr[v]){
            if(used[3][to]) continue;
            dfs3(to);
            siz[v] += siz[to];
      }
}

void dfs5(int v){
      used[4][v] = 1;
      for(int to : g[v])
            if(vis[v] == vis[to] && get(v) == get(to) && !used[4][to]){
                  u_s(v, to);
                  dfs5(to);
            }
}

void dfs6(int v){
      used[5][v] = 1;
      for(int to : g[v]){
            if(used[5][to] || get(v) != get(to)) continue;
            if(f_s(v) != f_s(to)){
                  G[f_s(v)].push_back(f_s(to));
                  G[f_s(to)].push_back(f_s(v));
            }
            dfs6(to);
      }
}

void dfs7(int v){
      used[6][v] = 1;
      sort(G[v].begin(), G[v].end());
      G[v].resize(unique(G[v].begin(), G[v].end()) - G[v].begin());
      for(int to : G[v]){
            if(used[6][to]) continue;
            dfs7(to);
      }
}

int TIN[N], FUP[N], TIMER;

void dfs8(int v, int pr = 0){
      used[7][v] = 1;
      TIN[v] = FUP[v] = ++ TIMER;
      for(int to : G[v]){
            if(to == pr) continue;
            if(used[7][to])
                  FUP[v] = min(FUP[v], TIN[v]);
            else {
                  dfs8(to, v);
                  FUP[v] = min(FUP[v], FUP[to]);
                  if(FUP[to] > TIN[v]){
                        ISB[{v, to}] = 1;
                        ISB[{to, v}] = 1;
                  }
            }
      }
}

void dfs9(int v){
      used[8][v] = 1;
      for(int to : G[v]){
            if(used[8][to]) continue;
            if(!ISB[{v, to}])
                  u_s(v, to);
            dfs9(to);
      }
}

int Sz, sZ[N], A[N];

void dfs10(int v, int pr = 0){
      used[9][v] = 1;
      for(int to : G[v]){
            if(pr == to) continue;
            if(used[9][to]) {
                  if(vis[to] && f_s(v) != f_s(to)) Sz += sZ[to];
            } else
                  if(f_s(v) == f_s(to))
                        dfs10(to);
                  else {
                        if(vis[to]) Sz += sZ[to];
                  }
      }
}

int Fup[N], Tin[N], Timer;

void dfs11(int v, int pr = 0){
      used[10][v] = 1;
      Fup[v] = Tin[v] = ++ Timer;
      int children = 0;
      for(int to : g[v]){
            if(to == pr || get(v) != get(to)) continue;
            if(used[10][to])
                  Fup[v] = min(Fup[v], Tin[to]);
            else {
                  dfs11(to, v);
                  Fup[v] = min(Fup[v], Fup[to]);
                  if(Fup[to] >= Tin[v] && pr)
                        vis[v] = 1;
                  children ++;
            }
      }
      if(children > 1 && !pr)
            vis[v] = 1;
}

void dfs4(int v, int pr = 0){
      ans += sz[v] * 1ll * (sz[v] - 1) * 1ll * (sz[v] - 2);
      dfs11(v);
      for(int i : vr[v])
            if(!used[4][i])
                  dfs5(i);
      dfs6(vr[v].front());
      dfs7(f_s(vr[v].front()));
      dfs8(f_s(vr[v].front()));
      for(int i : vr[v]){
            sZ[f_s(i)] = SZ[f_s(i)], A[i] = P[i];
      }
      dfs9(f_s(vr[v].front()));
      for(int i : vr[v]){
            if(!used[9][A[i]]){
                  Sz = SZ[f_s(i)];
                  dfs10(A[i]);
                  ans -= Sz * (Sz - 1) * (sz[v] - Sz);
            }
      }
      int S = 0;
      vector <int> vv;
      for(int i : vr[v]){
            vector <int> vec;
            int sum = 0;
            for(int to : g[i])
                  if(get(to) != get(i)){
                        if(get(to) == pr){
                              sum += siz[root] - siz[v];
                              vec.push_back(siz[root] - siz[v]);
                        } else {
                              sum += siz[get(to)];
                              vec.push_back(siz[get(to)]);
                        }
                  }
            for(int j : vec)
                  ans += j * 1ll * (sum - j);
            S += sum;
            vv.push_back(sum);
      }
      long long cur = 0;
      for(int i : vv)
            cur += i * 1ll * (S - i);
      ans += cur * 1ll * sz[v];
      long long cost = sz[v] - 1 + (sz[v] - 1) * 1ll * (sz[v] - 2);
      cost *= 2;
      ans += (siz[root] - siz[v]) * 1ll * cost;
      for(int to : gr[v]){
            if(to == pr) continue;
            ans += cost * 1ll * siz[to];
            dfs4(to, v);
      }
}

int main(){
      scanf("%d %d", &n, &m);

      for(int i = 1; i <= m; i ++){
            int u, v;
            scanf("%d %d", &u, &v);
            g[u].push_back(v);
            g[v].push_back(u);
      }

      for(int i = 1; i <= n; i ++)
            p[i] = P[i] = i, sz[i] = SZ[i] = 1;

      for(int i = 1; i <= n; i ++){
            if(!used[0][i]){
                  dfs(i);
                  dfs1(i);
                  dfs2(i);
                  root = get(i);
                  dfs3(get(i));
                  dfs4(get(i));
            }
      }

      cout << ans << endl;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:246:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &n, &m);
       ~~~~~^~~~~~~~~~~~~~~~~
count_triplets.cpp:250:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9848 KB Output is correct
2 Correct 9 ms 9848 KB Output is correct
3 Correct 10 ms 9900 KB Output is correct
4 Correct 10 ms 9952 KB Output is correct
5 Correct 10 ms 9984 KB Output is correct
6 Correct 9 ms 10032 KB Output is correct
7 Correct 11 ms 10032 KB Output is correct
8 Correct 10 ms 10040 KB Output is correct
9 Correct 10 ms 10064 KB Output is correct
10 Correct 10 ms 10164 KB Output is correct
11 Correct 10 ms 10164 KB Output is correct
12 Correct 10 ms 10164 KB Output is correct
13 Incorrect 11 ms 10164 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9848 KB Output is correct
2 Correct 9 ms 9848 KB Output is correct
3 Correct 10 ms 9900 KB Output is correct
4 Correct 10 ms 9952 KB Output is correct
5 Correct 10 ms 9984 KB Output is correct
6 Correct 9 ms 10032 KB Output is correct
7 Correct 11 ms 10032 KB Output is correct
8 Correct 10 ms 10040 KB Output is correct
9 Correct 10 ms 10064 KB Output is correct
10 Correct 10 ms 10164 KB Output is correct
11 Correct 10 ms 10164 KB Output is correct
12 Correct 10 ms 10164 KB Output is correct
13 Incorrect 11 ms 10164 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 37420 KB Output is correct
2 Correct 373 ms 37420 KB Output is correct
3 Correct 524 ms 43664 KB Output is correct
4 Correct 428 ms 43664 KB Output is correct
5 Correct 477 ms 43664 KB Output is correct
6 Correct 394 ms 43664 KB Output is correct
7 Correct 426 ms 43664 KB Output is correct
8 Correct 449 ms 43664 KB Output is correct
9 Correct 365 ms 43664 KB Output is correct
10 Correct 463 ms 43664 KB Output is correct
11 Correct 269 ms 43664 KB Output is correct
12 Correct 277 ms 43664 KB Output is correct
13 Correct 236 ms 43664 KB Output is correct
14 Correct 274 ms 43664 KB Output is correct
15 Correct 223 ms 43664 KB Output is correct
16 Correct 247 ms 43664 KB Output is correct
17 Correct 45 ms 43664 KB Output is correct
18 Correct 45 ms 43664 KB Output is correct
19 Correct 43 ms 43664 KB Output is correct
20 Correct 44 ms 43664 KB Output is correct
21 Correct 45 ms 43664 KB Output is correct
22 Correct 65 ms 43664 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 43664 KB Output is correct
2 Correct 439 ms 43664 KB Output is correct
3 Correct 565 ms 43664 KB Output is correct
4 Correct 571 ms 43664 KB Output is correct
5 Correct 629 ms 43664 KB Output is correct
6 Correct 634 ms 52332 KB Output is correct
7 Correct 641 ms 52332 KB Output is correct
8 Correct 684 ms 52332 KB Output is correct
9 Correct 702 ms 52332 KB Output is correct
10 Correct 634 ms 52332 KB Output is correct
11 Correct 551 ms 52332 KB Output is correct
12 Correct 551 ms 52332 KB Output is correct
13 Correct 430 ms 52332 KB Output is correct
14 Correct 373 ms 52332 KB Output is correct
15 Correct 335 ms 52332 KB Output is correct
16 Correct 199 ms 52332 KB Output is correct
17 Correct 353 ms 52332 KB Output is correct
18 Correct 561 ms 52332 KB Output is correct
19 Correct 561 ms 52332 KB Output is correct
20 Correct 588 ms 52332 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 52332 KB Output is correct
2 Correct 658 ms 52332 KB Output is correct
3 Correct 487 ms 52332 KB Output is correct
4 Correct 442 ms 52332 KB Output is correct
5 Correct 400 ms 52332 KB Output is correct
6 Correct 434 ms 52332 KB Output is correct
7 Correct 383 ms 52332 KB Output is correct
8 Correct 338 ms 52332 KB Output is correct
9 Correct 332 ms 52332 KB Output is correct
10 Correct 349 ms 52332 KB Output is correct
11 Correct 311 ms 52332 KB Output is correct
12 Correct 300 ms 52332 KB Output is correct
13 Correct 458 ms 52332 KB Output is correct
14 Correct 306 ms 52332 KB Output is correct
15 Correct 567 ms 52332 KB Output is correct
16 Correct 549 ms 52332 KB Output is correct
17 Correct 514 ms 52332 KB Output is correct
18 Correct 521 ms 52332 KB Output is correct
19 Correct 437 ms 52332 KB Output is correct
20 Correct 442 ms 52332 KB Output is correct
21 Correct 447 ms 52332 KB Output is correct
22 Correct 303 ms 52332 KB Output is correct
23 Correct 262 ms 52332 KB Output is correct
24 Correct 434 ms 52332 KB Output is correct
25 Correct 406 ms 52332 KB Output is correct
26 Correct 448 ms 52332 KB Output is correct
27 Correct 465 ms 52332 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9848 KB Output is correct
2 Correct 9 ms 9848 KB Output is correct
3 Correct 10 ms 9900 KB Output is correct
4 Correct 10 ms 9952 KB Output is correct
5 Correct 10 ms 9984 KB Output is correct
6 Correct 9 ms 10032 KB Output is correct
7 Correct 11 ms 10032 KB Output is correct
8 Correct 10 ms 10040 KB Output is correct
9 Correct 10 ms 10064 KB Output is correct
10 Correct 10 ms 10164 KB Output is correct
11 Correct 10 ms 10164 KB Output is correct
12 Correct 10 ms 10164 KB Output is correct
13 Incorrect 11 ms 10164 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9848 KB Output is correct
2 Correct 9 ms 9848 KB Output is correct
3 Correct 10 ms 9900 KB Output is correct
4 Correct 10 ms 9952 KB Output is correct
5 Correct 10 ms 9984 KB Output is correct
6 Correct 9 ms 10032 KB Output is correct
7 Correct 11 ms 10032 KB Output is correct
8 Correct 10 ms 10040 KB Output is correct
9 Correct 10 ms 10064 KB Output is correct
10 Correct 10 ms 10164 KB Output is correct
11 Correct 10 ms 10164 KB Output is correct
12 Correct 10 ms 10164 KB Output is correct
13 Incorrect 11 ms 10164 KB Output isn't correct
14 Halted 0 ms 0 KB -