oj.uz

Submission #49376

# Submission time Handle Problem Language Result Execution time Memory
49376 2018-05-28T03:54:02 Z mirbek01 Duathlon (APIO18_duathlon) C++17
31 / 100
 522 ms 33520 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];

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

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:95: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:99: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 4984 KB Output is correct
2 Correct 6 ms 5092 KB Output is correct
3 Correct 6 ms 5092 KB Output is correct
4 Correct 7 ms 5168 KB Output is correct
5 Correct 7 ms 5204 KB Output is correct
6 Correct 6 ms 5204 KB Output is correct
7 Incorrect 7 ms 5280 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 6 ms 5092 KB Output is correct
3 Correct 6 ms 5092 KB Output is correct
4 Correct 7 ms 5168 KB Output is correct
5 Correct 7 ms 5204 KB Output is correct
6 Correct 6 ms 5204 KB Output is correct
7 Incorrect 7 ms 5280 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 253 ms 28396 KB Output is correct
2 Correct 199 ms 28396 KB Output is correct
3 Correct 371 ms 28428 KB Output is correct
4 Correct 331 ms 28744 KB Output is correct
5 Correct 300 ms 28744 KB Output is correct
6 Correct 258 ms 28744 KB Output is correct
7 Correct 269 ms 28744 KB Output is correct
8 Correct 317 ms 28744 KB Output is correct
9 Correct 378 ms 28744 KB Output is correct
10 Correct 369 ms 28744 KB Output is correct
11 Correct 247 ms 28744 KB Output is correct
12 Correct 206 ms 28744 KB Output is correct
13 Correct 211 ms 28744 KB Output is correct
14 Correct 157 ms 28744 KB Output is correct
15 Correct 136 ms 28744 KB Output is correct
16 Correct 160 ms 28744 KB Output is correct
17 Correct 14 ms 28744 KB Output is correct
18 Correct 13 ms 28744 KB Output is correct
19 Correct 13 ms 28744 KB Output is correct
20 Correct 12 ms 28744 KB Output is correct
21 Correct 13 ms 28744 KB Output is correct
22 Correct 13 ms 28744 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 28744 KB Output is correct
2 Correct 427 ms 28744 KB Output is correct
3 Correct 479 ms 28744 KB Output is correct
4 Correct 434 ms 28744 KB Output is correct
5 Correct 461 ms 28744 KB Output is correct
6 Correct 451 ms 33520 KB Output is correct
7 Correct 459 ms 33520 KB Output is correct
8 Correct 456 ms 33520 KB Output is correct
9 Correct 452 ms 33520 KB Output is correct
10 Correct 404 ms 33520 KB Output is correct
11 Correct 412 ms 33520 KB Output is correct
12 Correct 408 ms 33520 KB Output is correct
13 Correct 435 ms 33520 KB Output is correct
14 Correct 352 ms 33520 KB Output is correct
15 Correct 302 ms 33520 KB Output is correct
16 Correct 180 ms 33520 KB Output is correct
17 Correct 370 ms 33520 KB Output is correct
18 Correct 391 ms 33520 KB Output is correct
19 Correct 373 ms 33520 KB Output is correct
20 Correct 386 ms 33520 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 6 ms 5092 KB Output is correct
3 Correct 6 ms 5092 KB Output is correct
4 Correct 7 ms 5168 KB Output is correct
5 Correct 7 ms 5204 KB Output is correct
6 Correct 6 ms 5204 KB Output is correct
7 Incorrect 7 ms 5280 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 6 ms 5092 KB Output is correct
3 Correct 6 ms 5092 KB Output is correct
4 Correct 7 ms 5168 KB Output is correct
5 Correct 7 ms 5204 KB Output is correct
6 Correct 6 ms 5204 KB Output is correct
7 Incorrect 7 ms 5280 KB Output isn't correct
8 Halted 0 ms 0 KB -