oj.uz

Submission #49385

# Submission time Handle Problem Language Result Execution time Memory
49385 2018-05-28T07:08:53 Z mirbek01 Duathlon (APIO18_duathlon) C++17
31 / 100
 648 ms 47800 KB 
# include <bits/stdc++.h>
# define int long long

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);
      ans += (siz[root] - siz[v]) * 1ll * (siz[v] - sz[v]) * 1ll * sz[v] * 1ll * 2;
      long long cost = (sz[v] - 1) + (sz[v] - 1) * 1ll * (sz[v] - 2), S = 0;
      cost *= 2;
      ans += (siz[root] - siz[v]) * 1ll * cost;
      vector <int> vv;
      for(int i : vr[v]){
            vector <int> vec;
            for(int to : g[i])
                  if(get(to) != v && get(to) != pr)
                        vec.push_back(get(to));
            sort(vec.begin(), vec.end());
            vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
            int sum = 0;
            for(int j : vec)
                  sum += siz[j];
            for(int j : vec)
                  ans += siz[j] * 1ll * (sum - siz[j]);
            vv.push_back(sum);
            S += sum;
      }
      for(int i : vv)
            ans += i * 1ll * (S - i);
      for(int to : gr[v]){
            if(to == pr) continue;
            ans += siz[to] * 1ll * cost;
            dfs4(to, v);
      }
}

main(){
      cin>>n>>m;

      for(int i = 1; i <= m; i ++){
            int u, v;
            cin>>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;
}
/**
7 8
1 2
1 3
2 3
4 5
4 6
5 6
1 4
1 7
**/

Compilation message

count_triplets.cpp:113:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 34268 KB Output is correct
2 Correct 335 ms 34268 KB Output is correct
3 Correct 467 ms 38996 KB Output is correct
4 Correct 345 ms 38996 KB Output is correct
5 Correct 450 ms 38996 KB Output is correct
6 Correct 514 ms 38996 KB Output is correct
7 Correct 486 ms 38996 KB Output is correct
8 Correct 408 ms 38996 KB Output is correct
9 Correct 476 ms 38996 KB Output is correct
10 Correct 505 ms 38996 KB Output is correct
11 Correct 339 ms 38996 KB Output is correct
12 Correct 349 ms 38996 KB Output is correct
13 Correct 312 ms 38996 KB Output is correct
14 Correct 331 ms 38996 KB Output is correct
15 Correct 231 ms 38996 KB Output is correct
16 Correct 242 ms 38996 KB Output is correct
17 Correct 43 ms 38996 KB Output is correct
18 Correct 30 ms 38996 KB Output is correct
19 Correct 32 ms 38996 KB Output is correct
20 Correct 30 ms 38996 KB Output is correct
21 Correct 29 ms 38996 KB Output is correct
22 Correct 47 ms 38996 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 38996 KB Output is correct
2 Correct 597 ms 38996 KB Output is correct
3 Correct 585 ms 38996 KB Output is correct
4 Correct 492 ms 38996 KB Output is correct
5 Correct 469 ms 38996 KB Output is correct
6 Correct 560 ms 47800 KB Output is correct
7 Correct 586 ms 47800 KB Output is correct
8 Correct 545 ms 47800 KB Output is correct
9 Correct 609 ms 47800 KB Output is correct
10 Correct 628 ms 47800 KB Output is correct
11 Correct 559 ms 47800 KB Output is correct
12 Correct 648 ms 47800 KB Output is correct
13 Correct 571 ms 47800 KB Output is correct
14 Correct 462 ms 47800 KB Output is correct
15 Correct 414 ms 47800 KB Output is correct
16 Correct 260 ms 47800 KB Output is correct
17 Correct 531 ms 47800 KB Output is correct
18 Correct 464 ms 47800 KB Output is correct
19 Correct 411 ms 47800 KB Output is correct
20 Correct 469 ms 47800 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 505 ms 47800 KB Output is correct
2 Correct 630 ms 47800 KB Output is correct
3 Incorrect 489 ms 47800 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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