oj.uz

Submission #49405

# Submission time Handle Problem Language Result Execution time Memory
49405 2018-05-28T10:35:03 Z mirbek01 Duathlon (APIO18_duathlon) C++17
31 / 100
 682 ms 45092 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);
      vector <int> vv;
      int S = 0;
      for(int i : vr[v]){
            vector <int> vec;
            bool fl = 0;
            for(int to : g[i]){
                  if(get(to) != v && get(to) != pr)
                        vec.push_back(get(to));
                  if(get(to) == pr) fl = 1;
            }
            sort(vec.begin(), vec.end());
            vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
            int sum = 0;
            for(int j : vec)
                  sum += siz[j];
            if(fl) {
                  if(!sum)
                        sum += siz[root] - siz[v];
                  else{
                        S += siz[root] - siz[v];
                        vv.push_back(siz[root] - siz[v]);
                  }
            }
            S += sum;
            for(int j : vec)
                  ans += siz[j] * 1ll * (sum - siz[j]);
            vv.push_back(sum);
      }
      long long cur = 0;
      for(int i : vv){
            cur += (S - i) * 1ll * i;
            ans += (sz[v] - 1) * 1ll * (siz[root] - sz[v] - i) * 2ll;
      }
      ans += cur * 1ll * sz[v];
      for(int to : gr[v]){
            if(to == pr) continue;
            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:124: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:128: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 7420 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 9 ms 7524 KB Output is correct
4 Correct 9 ms 7524 KB Output is correct
5 Correct 7 ms 7524 KB Output is correct
6 Correct 8 ms 7528 KB Output is correct
7 Correct 8 ms 7528 KB Output is correct
8 Incorrect 7 ms 7540 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 7420 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 9 ms 7524 KB Output is correct
4 Correct 9 ms 7524 KB Output is correct
5 Correct 7 ms 7524 KB Output is correct
6 Correct 8 ms 7528 KB Output is correct
7 Correct 8 ms 7528 KB Output is correct
8 Incorrect 7 ms 7540 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 214 ms 31828 KB Output is correct
2 Correct 273 ms 31880 KB Output is correct
3 Correct 444 ms 35996 KB Output is correct
4 Correct 366 ms 35996 KB Output is correct
5 Correct 372 ms 35996 KB Output is correct
6 Correct 440 ms 35996 KB Output is correct
7 Correct 431 ms 35996 KB Output is correct
8 Correct 462 ms 35996 KB Output is correct
9 Correct 339 ms 35996 KB Output is correct
10 Correct 414 ms 35996 KB Output is correct
11 Correct 305 ms 35996 KB Output is correct
12 Correct 308 ms 35996 KB Output is correct
13 Correct 282 ms 35996 KB Output is correct
14 Correct 219 ms 35996 KB Output is correct
15 Correct 282 ms 35996 KB Output is correct
16 Correct 172 ms 35996 KB Output is correct
17 Correct 26 ms 35996 KB Output is correct
18 Correct 27 ms 35996 KB Output is correct
19 Correct 29 ms 35996 KB Output is correct
20 Correct 26 ms 35996 KB Output is correct
21 Correct 29 ms 35996 KB Output is correct
22 Correct 30 ms 35996 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 35996 KB Output is correct
2 Correct 546 ms 35996 KB Output is correct
3 Correct 589 ms 35996 KB Output is correct
4 Correct 511 ms 35996 KB Output is correct
5 Correct 480 ms 35996 KB Output is correct
6 Correct 682 ms 45092 KB Output is correct
7 Correct 626 ms 45092 KB Output is correct
8 Correct 617 ms 45092 KB Output is correct
9 Correct 625 ms 45092 KB Output is correct
10 Correct 428 ms 45092 KB Output is correct
11 Correct 539 ms 45092 KB Output is correct
12 Correct 558 ms 45092 KB Output is correct
13 Correct 552 ms 45092 KB Output is correct
14 Correct 444 ms 45092 KB Output is correct
15 Correct 400 ms 45092 KB Output is correct
16 Correct 283 ms 45092 KB Output is correct
17 Correct 411 ms 45092 KB Output is correct
18 Correct 482 ms 45092 KB Output is correct
19 Correct 445 ms 45092 KB Output is correct
20 Correct 476 ms 45092 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 45092 KB Output is correct
2 Correct 594 ms 45092 KB Output is correct
3 Incorrect 527 ms 45092 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 7420 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 9 ms 7524 KB Output is correct
4 Correct 9 ms 7524 KB Output is correct
5 Correct 7 ms 7524 KB Output is correct
6 Correct 8 ms 7528 KB Output is correct
7 Correct 8 ms 7528 KB Output is correct
8 Incorrect 7 ms 7540 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 7420 KB Output is correct
2 Correct 9 ms 7524 KB Output is correct
3 Correct 9 ms 7524 KB Output is correct
4 Correct 9 ms 7524 KB Output is correct
5 Correct 7 ms 7524 KB Output is correct
6 Correct 8 ms 7528 KB Output is correct
7 Correct 8 ms 7528 KB Output is correct
8 Incorrect 7 ms 7540 KB Output isn't correct
9 Halted 0 ms 0 KB -