oj.uz

Submission #49447

# Submission time Handle Problem Language Result Execution time Memory
49447 2018-05-29T05:38:07 Z mirbek01 Duathlon (APIO18_duathlon) C++17
66 / 100
 682 ms 44564 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

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

void dfs(int v, int pr = 0){
      used[0][v] = 1;
      tin[v] = fup[v] = ++ timer;
      int children = 0;
      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;
                  }
                  if(fup[to] >= tin[v] && pr)
                        vis[v] = 1;
                  ++ children;
            }
      }
      if(pr == 0 && children == 0)
            vis[v] = 1;
}

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];
      }
}

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 dfs4(int v, int pr = 0){
      ans += sz[v] * 1ll * (sz[v] - 1) * 1ll * (sz[v] - 2);
      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] = 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:122: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:126: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 7380 KB Output is correct
2 Correct 10 ms 7472 KB Output is correct
3 Correct 10 ms 7472 KB Output is correct
4 Correct 7 ms 7524 KB Output is correct
5 Correct 8 ms 7524 KB Output is correct
6 Correct 9 ms 7524 KB Output is correct
7 Correct 8 ms 7556 KB Output is correct
8 Incorrect 9 ms 7556 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7380 KB Output is correct
2 Correct 10 ms 7472 KB Output is correct
3 Correct 10 ms 7472 KB Output is correct
4 Correct 7 ms 7524 KB Output is correct
5 Correct 8 ms 7524 KB Output is correct
6 Correct 9 ms 7524 KB Output is correct
7 Correct 8 ms 7556 KB Output is correct
8 Incorrect 9 ms 7556 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 276 ms 31780 KB Output is correct
2 Correct 287 ms 31800 KB Output is correct
3 Correct 431 ms 35660 KB Output is correct
4 Correct 342 ms 35660 KB Output is correct
5 Correct 353 ms 35660 KB Output is correct
6 Correct 336 ms 35660 KB Output is correct
7 Correct 380 ms 35660 KB Output is correct
8 Correct 452 ms 35660 KB Output is correct
9 Correct 378 ms 35660 KB Output is correct
10 Correct 306 ms 35660 KB Output is correct
11 Correct 265 ms 35660 KB Output is correct
12 Correct 279 ms 35660 KB Output is correct
13 Correct 239 ms 35660 KB Output is correct
14 Correct 266 ms 35660 KB Output is correct
15 Correct 202 ms 35660 KB Output is correct
16 Correct 222 ms 35660 KB Output is correct
17 Correct 30 ms 35660 KB Output is correct
18 Correct 29 ms 35660 KB Output is correct
19 Correct 30 ms 35660 KB Output is correct
20 Correct 39 ms 35660 KB Output is correct
21 Correct 28 ms 35660 KB Output is correct
22 Correct 35 ms 35660 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 35660 KB Output is correct
2 Correct 540 ms 35660 KB Output is correct
3 Correct 546 ms 35660 KB Output is correct
4 Correct 537 ms 35660 KB Output is correct
5 Correct 682 ms 35660 KB Output is correct
6 Correct 586 ms 44564 KB Output is correct
7 Correct 582 ms 44564 KB Output is correct
8 Correct 624 ms 44564 KB Output is correct
9 Correct 609 ms 44564 KB Output is correct
10 Correct 519 ms 44564 KB Output is correct
11 Correct 497 ms 44564 KB Output is correct
12 Correct 513 ms 44564 KB Output is correct
13 Correct 505 ms 44564 KB Output is correct
14 Correct 416 ms 44564 KB Output is correct
15 Correct 354 ms 44564 KB Output is correct
16 Correct 181 ms 44564 KB Output is correct
17 Correct 450 ms 44564 KB Output is correct
18 Correct 377 ms 44564 KB Output is correct
19 Correct 423 ms 44564 KB Output is correct
20 Correct 371 ms 44564 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 500 ms 44564 KB Output is correct
2 Correct 445 ms 44564 KB Output is correct
3 Correct 409 ms 44564 KB Output is correct
4 Correct 328 ms 44564 KB Output is correct
5 Correct 330 ms 44564 KB Output is correct
6 Correct 323 ms 44564 KB Output is correct
7 Correct 278 ms 44564 KB Output is correct
8 Correct 272 ms 44564 KB Output is correct
9 Correct 267 ms 44564 KB Output is correct
10 Correct 224 ms 44564 KB Output is correct
11 Correct 241 ms 44564 KB Output is correct
12 Correct 263 ms 44564 KB Output is correct
13 Correct 248 ms 44564 KB Output is correct
14 Correct 274 ms 44564 KB Output is correct
15 Correct 518 ms 44564 KB Output is correct
16 Correct 556 ms 44564 KB Output is correct
17 Correct 460 ms 44564 KB Output is correct
18 Correct 498 ms 44564 KB Output is correct
19 Correct 429 ms 44564 KB Output is correct
20 Correct 340 ms 44564 KB Output is correct
21 Correct 274 ms 44564 KB Output is correct
22 Correct 248 ms 44564 KB Output is correct
23 Correct 274 ms 44564 KB Output is correct
24 Correct 374 ms 44564 KB Output is correct
25 Correct 525 ms 44564 KB Output is correct
26 Correct 426 ms 44564 KB Output is correct
27 Correct 428 ms 44564 KB Output is correct

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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