oj.uz

Submission #49377

# Submission time Handle Problem Language Result Execution time Memory
49377 2018-05-28T04:01:43 Z mirbek01 Duathlon (APIO18_duathlon) C++17
31 / 100
 510 ms 33980 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

int n, m, used[10][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];

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;
      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];
      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 += siz[to] * 1ll * cost;
            ans += siz[to] * 1ll * (siz[root] - siz[to] - sz[v]) * 1ll * sz[v];
            dfs4(to, v);
      }
}

bool flag;

void dfs5(int v, int pr = 0){
      used[4][v] = 1;
      for(int to : g[v]){
            if(to == pr) continue;
            if(used[4][to])
                  flag = 1;
            else
                  dfs5(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;
      long long preans;
      for(int i = 1; i <= n; i ++){
            if(!used[0][i]){
                  preans = ans;
                  flag = 0;
                  dfs5(i);
                  dfs(i);
                  dfs1(i);
                  dfs2(i);
                  root = get(i);
                  dfs3(get(i));
                  dfs4(get(i));
                  if(flag){
                        ans = preans;
                        ans += siz[root] * 1ll * (siz[root] - 1) * 1ll * (siz[root] - 2);
                  }
            }
      }

      cout << ans << endl;
}
/**
4 4
1 2
2 3
3 4
4 2

6 7
1 2
1 3
2 3
4 5
4 6
5 6
2 4
**/

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:108: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:112: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 5 ms 4988 KB Output is correct
2 Correct 5 ms 5092 KB Output is correct
3 Correct 5 ms 5172 KB Output is correct
4 Correct 6 ms 5184 KB Output is correct
5 Correct 7 ms 5216 KB Output is correct
6 Correct 6 ms 5220 KB Output is correct
7 Incorrect 5 ms 5276 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4988 KB Output is correct
2 Correct 5 ms 5092 KB Output is correct
3 Correct 5 ms 5172 KB Output is correct
4 Correct 6 ms 5184 KB Output is correct
5 Correct 7 ms 5216 KB Output is correct
6 Correct 6 ms 5220 KB Output is correct
7 Incorrect 5 ms 5276 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 193 ms 28728 KB Output is correct
2 Correct 243 ms 28728 KB Output is correct
3 Correct 390 ms 28764 KB Output is correct
4 Correct 372 ms 29056 KB Output is correct
5 Correct 347 ms 29056 KB Output is correct
6 Correct 342 ms 29056 KB Output is correct
7 Correct 387 ms 29056 KB Output is correct
8 Correct 424 ms 29056 KB Output is correct
9 Correct 377 ms 29056 KB Output is correct
10 Correct 354 ms 29056 KB Output is correct
11 Correct 261 ms 29056 KB Output is correct
12 Correct 274 ms 29056 KB Output is correct
13 Correct 215 ms 29056 KB Output is correct
14 Correct 270 ms 29056 KB Output is correct
15 Correct 185 ms 29056 KB Output is correct
16 Correct 167 ms 29056 KB Output is correct
17 Correct 15 ms 29056 KB Output is correct
18 Correct 15 ms 29056 KB Output is correct
19 Correct 14 ms 29056 KB Output is correct
20 Correct 56 ms 29056 KB Output is correct
21 Correct 14 ms 29056 KB Output is correct
22 Correct 14 ms 29056 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 29056 KB Output is correct
2 Correct 419 ms 29056 KB Output is correct
3 Correct 420 ms 29056 KB Output is correct
4 Correct 450 ms 29056 KB Output is correct
5 Correct 411 ms 29056 KB Output is correct
6 Correct 465 ms 33980 KB Output is correct
7 Correct 476 ms 33980 KB Output is correct
8 Correct 502 ms 33980 KB Output is correct
9 Correct 510 ms 33980 KB Output is correct
10 Correct 439 ms 33980 KB Output is correct
11 Correct 358 ms 33980 KB Output is correct
12 Correct 460 ms 33980 KB Output is correct
13 Correct 476 ms 33980 KB Output is correct
14 Correct 358 ms 33980 KB Output is correct
15 Correct 391 ms 33980 KB Output is correct
16 Correct 156 ms 33980 KB Output is correct
17 Correct 416 ms 33980 KB Output is correct
18 Correct 415 ms 33980 KB Output is correct
19 Correct 385 ms 33980 KB Output is correct
20 Correct 395 ms 33980 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4988 KB Output is correct
2 Correct 5 ms 5092 KB Output is correct
3 Correct 5 ms 5172 KB Output is correct
4 Correct 6 ms 5184 KB Output is correct
5 Correct 7 ms 5216 KB Output is correct
6 Correct 6 ms 5220 KB Output is correct
7 Incorrect 5 ms 5276 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4988 KB Output is correct
2 Correct 5 ms 5092 KB Output is correct
3 Correct 5 ms 5172 KB Output is correct
4 Correct 6 ms 5184 KB Output is correct
5 Correct 7 ms 5216 KB Output is correct
6 Correct 6 ms 5220 KB Output is correct
7 Incorrect 5 ms 5276 KB Output isn't correct
8 Halted 0 ms 0 KB -