oj.uz

Submission #49444

# Submission time Handle Problem Language Result Execution time Memory
49444 2018-05-29T04:50:33 Z mirbek01 Duathlon (APIO18_duathlon) C++17
66 / 100
 723 ms 44224 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, m, used[4][N], root;
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;
      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;
                  }
            }
      }
}

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;
      sort(gr[v].begin(), gr[v].end());
      gr[v].resize(unique(gr[v].begin(), gr[v].end()) - gr[v].begin());
      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:118: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:122: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 7 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 7 ms 7472 KB Output is correct
4 Correct 8 ms 7548 KB Output is correct
5 Correct 9 ms 7552 KB Output is correct
6 Correct 10 ms 7584 KB Output is correct
7 Correct 9 ms 7712 KB Output is correct
8 Incorrect 9 ms 7712 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 7 ms 7472 KB Output is correct
4 Correct 8 ms 7548 KB Output is correct
5 Correct 9 ms 7552 KB Output is correct
6 Correct 10 ms 7584 KB Output is correct
7 Correct 9 ms 7712 KB Output is correct
8 Incorrect 9 ms 7712 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 370 ms 31912 KB Output is correct
2 Correct 282 ms 31912 KB Output is correct
3 Correct 439 ms 35272 KB Output is correct
4 Correct 254 ms 35272 KB Output is correct
5 Correct 344 ms 35272 KB Output is correct
6 Correct 373 ms 35272 KB Output is correct
7 Correct 456 ms 35272 KB Output is correct
8 Correct 364 ms 35272 KB Output is correct
9 Correct 456 ms 35272 KB Output is correct
10 Correct 410 ms 35272 KB Output is correct
11 Correct 272 ms 35272 KB Output is correct
12 Correct 283 ms 35272 KB Output is correct
13 Correct 251 ms 35272 KB Output is correct
14 Correct 280 ms 35272 KB Output is correct
15 Correct 214 ms 35272 KB Output is correct
16 Correct 199 ms 35272 KB Output is correct
17 Correct 31 ms 35272 KB Output is correct
18 Correct 31 ms 35272 KB Output is correct
19 Correct 29 ms 35272 KB Output is correct
20 Correct 29 ms 35272 KB Output is correct
21 Correct 30 ms 35272 KB Output is correct
22 Correct 30 ms 35272 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 35272 KB Output is correct
2 Correct 568 ms 35272 KB Output is correct
3 Correct 548 ms 35272 KB Output is correct
4 Correct 454 ms 35272 KB Output is correct
5 Correct 412 ms 35272 KB Output is correct
6 Correct 614 ms 44224 KB Output is correct
7 Correct 723 ms 44224 KB Output is correct
8 Correct 710 ms 44224 KB Output is correct
9 Correct 506 ms 44224 KB Output is correct
10 Correct 496 ms 44224 KB Output is correct
11 Correct 539 ms 44224 KB Output is correct
12 Correct 551 ms 44224 KB Output is correct
13 Correct 542 ms 44224 KB Output is correct
14 Correct 430 ms 44224 KB Output is correct
15 Correct 386 ms 44224 KB Output is correct
16 Correct 249 ms 44224 KB Output is correct
17 Correct 495 ms 44224 KB Output is correct
18 Correct 498 ms 44224 KB Output is correct
19 Correct 478 ms 44224 KB Output is correct
20 Correct 459 ms 44224 KB Output is correct

Subtask #6
15.0 / 15.0

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

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 44224 KB Output is correct
2 Correct 521 ms 44224 KB Output is correct
3 Correct 473 ms 44224 KB Output is correct
4 Correct 300 ms 44224 KB Output is correct
5 Correct 248 ms 44224 KB Output is correct
6 Correct 308 ms 44224 KB Output is correct
7 Correct 209 ms 44224 KB Output is correct
8 Correct 270 ms 44224 KB Output is correct
9 Correct 206 ms 44224 KB Output is correct
10 Correct 242 ms 44224 KB Output is correct
11 Correct 249 ms 44224 KB Output is correct
12 Correct 267 ms 44224 KB Output is correct
13 Correct 251 ms 44224 KB Output is correct
14 Correct 265 ms 44224 KB Output is correct
15 Correct 552 ms 44224 KB Output is correct
16 Correct 529 ms 44224 KB Output is correct
17 Correct 451 ms 44224 KB Output is correct
18 Correct 457 ms 44224 KB Output is correct
19 Correct 427 ms 44224 KB Output is correct
20 Correct 425 ms 44224 KB Output is correct
21 Correct 406 ms 44224 KB Output is correct
22 Correct 358 ms 44224 KB Output is correct
23 Correct 248 ms 44224 KB Output is correct
24 Correct 475 ms 44224 KB Output is correct
25 Correct 545 ms 44224 KB Output is correct
26 Correct 406 ms 44224 KB Output is correct
27 Correct 349 ms 44224 KB Output is correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 7 ms 7472 KB Output is correct
4 Correct 8 ms 7548 KB Output is correct
5 Correct 9 ms 7552 KB Output is correct
6 Correct 10 ms 7584 KB Output is correct
7 Correct 9 ms 7712 KB Output is correct
8 Incorrect 9 ms 7712 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7416 KB Output is correct
2 Correct 8 ms 7416 KB Output is correct
3 Correct 7 ms 7472 KB Output is correct
4 Correct 8 ms 7548 KB Output is correct
5 Correct 9 ms 7552 KB Output is correct
6 Correct 10 ms 7584 KB Output is correct
7 Correct 9 ms 7712 KB Output is correct
8 Incorrect 9 ms 7712 KB Output isn't correct
9 Halted 0 ms 0 KB -