oj.uz

Submission #49510

# Submission time Handle Problem Language Result Execution time Memory
49510 2018-05-30T06:24:03 Z mirbek01 Duathlon (APIO18_duathlon) C++17
66 / 100
 746 ms 52412 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;
      if(vis[v])
            Sz -= sZ[v];
      for(int to : G[v]){
            if(pr == to || used[9][to]) continue;
            if(f_s(v) == f_s(to))
                  dfs10(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 * 1ll * ((sz[v] - SZ[f_s(i)]) * 1ll * (sz[v] - SZ[f_s(i)] - 1));
            }
      }
      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:242: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:246: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 9740 KB Output is correct
2 Correct 9 ms 9828 KB Output is correct
3 Correct 9 ms 9908 KB Output is correct
4 Correct 9 ms 10048 KB Output is correct
5 Correct 9 ms 10048 KB Output is correct
6 Correct 9 ms 10048 KB Output is correct
7 Correct 10 ms 10048 KB Output is correct
8 Correct 9 ms 10048 KB Output is correct
9 Correct 9 ms 10048 KB Output is correct
10 Correct 9 ms 10132 KB Output is correct
11 Correct 9 ms 10132 KB Output is correct
12 Correct 9 ms 10132 KB Output is correct
13 Incorrect 9 ms 10132 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 9740 KB Output is correct
2 Correct 9 ms 9828 KB Output is correct
3 Correct 9 ms 9908 KB Output is correct
4 Correct 9 ms 10048 KB Output is correct
5 Correct 9 ms 10048 KB Output is correct
6 Correct 9 ms 10048 KB Output is correct
7 Correct 10 ms 10048 KB Output is correct
8 Correct 9 ms 10048 KB Output is correct
9 Correct 9 ms 10048 KB Output is correct
10 Correct 9 ms 10132 KB Output is correct
11 Correct 9 ms 10132 KB Output is correct
12 Correct 9 ms 10132 KB Output is correct
13 Incorrect 9 ms 10132 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 404 ms 37452 KB Output is correct
2 Correct 362 ms 37452 KB Output is correct
3 Correct 489 ms 43620 KB Output is correct
4 Correct 410 ms 43620 KB Output is correct
5 Correct 425 ms 43620 KB Output is correct
6 Correct 509 ms 43620 KB Output is correct
7 Correct 471 ms 43620 KB Output is correct
8 Correct 460 ms 43620 KB Output is correct
9 Correct 433 ms 43620 KB Output is correct
10 Correct 381 ms 43620 KB Output is correct
11 Correct 281 ms 43620 KB Output is correct
12 Correct 346 ms 43620 KB Output is correct
13 Correct 346 ms 43620 KB Output is correct
14 Correct 329 ms 43620 KB Output is correct
15 Correct 290 ms 43620 KB Output is correct
16 Correct 232 ms 43620 KB Output is correct
17 Correct 40 ms 43620 KB Output is correct
18 Correct 49 ms 43620 KB Output is correct
19 Correct 46 ms 43620 KB Output is correct
20 Correct 49 ms 43620 KB Output is correct
21 Correct 45 ms 43620 KB Output is correct
22 Correct 46 ms 43620 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 43620 KB Output is correct
2 Correct 503 ms 43620 KB Output is correct
3 Correct 589 ms 43620 KB Output is correct
4 Correct 615 ms 43620 KB Output is correct
5 Correct 549 ms 43620 KB Output is correct
6 Correct 674 ms 52412 KB Output is correct
7 Correct 746 ms 52412 KB Output is correct
8 Correct 697 ms 52412 KB Output is correct
9 Correct 701 ms 52412 KB Output is correct
10 Correct 642 ms 52412 KB Output is correct
11 Correct 673 ms 52412 KB Output is correct
12 Correct 600 ms 52412 KB Output is correct
13 Correct 553 ms 52412 KB Output is correct
14 Correct 459 ms 52412 KB Output is correct
15 Correct 457 ms 52412 KB Output is correct
16 Correct 343 ms 52412 KB Output is correct
17 Correct 547 ms 52412 KB Output is correct
18 Correct 553 ms 52412 KB Output is correct
19 Correct 737 ms 52412 KB Output is correct
20 Correct 535 ms 52412 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 604 ms 52412 KB Output is correct
2 Correct 630 ms 52412 KB Output is correct
3 Correct 550 ms 52412 KB Output is correct
4 Correct 488 ms 52412 KB Output is correct
5 Correct 409 ms 52412 KB Output is correct
6 Correct 439 ms 52412 KB Output is correct
7 Correct 295 ms 52412 KB Output is correct
8 Correct 306 ms 52412 KB Output is correct
9 Correct 297 ms 52412 KB Output is correct
10 Correct 311 ms 52412 KB Output is correct
11 Correct 311 ms 52412 KB Output is correct
12 Correct 296 ms 52412 KB Output is correct
13 Correct 294 ms 52412 KB Output is correct
14 Correct 286 ms 52412 KB Output is correct
15 Correct 527 ms 52412 KB Output is correct
16 Correct 563 ms 52412 KB Output is correct
17 Correct 617 ms 52412 KB Output is correct
18 Correct 502 ms 52412 KB Output is correct
19 Correct 463 ms 52412 KB Output is correct
20 Correct 445 ms 52412 KB Output is correct
21 Correct 432 ms 52412 KB Output is correct
22 Correct 276 ms 52412 KB Output is correct
23 Correct 245 ms 52412 KB Output is correct
24 Correct 396 ms 52412 KB Output is correct
25 Correct 375 ms 52412 KB Output is correct
26 Correct 486 ms 52412 KB Output is correct
27 Correct 456 ms 52412 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9740 KB Output is correct
2 Correct 9 ms 9828 KB Output is correct
3 Correct 9 ms 9908 KB Output is correct
4 Correct 9 ms 10048 KB Output is correct
5 Correct 9 ms 10048 KB Output is correct
6 Correct 9 ms 10048 KB Output is correct
7 Correct 10 ms 10048 KB Output is correct
8 Correct 9 ms 10048 KB Output is correct
9 Correct 9 ms 10048 KB Output is correct
10 Correct 9 ms 10132 KB Output is correct
11 Correct 9 ms 10132 KB Output is correct
12 Correct 9 ms 10132 KB Output is correct
13 Incorrect 9 ms 10132 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 9740 KB Output is correct
2 Correct 9 ms 9828 KB Output is correct
3 Correct 9 ms 9908 KB Output is correct
4 Correct 9 ms 10048 KB Output is correct
5 Correct 9 ms 10048 KB Output is correct
6 Correct 9 ms 10048 KB Output is correct
7 Correct 10 ms 10048 KB Output is correct
8 Correct 9 ms 10048 KB Output is correct
9 Correct 9 ms 10048 KB Output is correct
10 Correct 9 ms 10132 KB Output is correct
11 Correct 9 ms 10132 KB Output is correct
12 Correct 9 ms 10132 KB Output is correct
13 Incorrect 9 ms 10132 KB Output isn't correct
14 Halted 0 ms 0 KB -