답안 #951448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
951448	2024-03-22T01:30:56 Z	abczz	철인 이종 경기 (APIO18_duathlon)	C++14	31 / 100	154 ms	49084 KB

count_triplets

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <deque>
#include <queue>
#include <map>
#define ll long long

using namespace std;

bool visited[100000];
ll n, m, k, a, b, g, cnt, f, rt, apcnt, low[100000], st[100000], sz[200000], dp[200000];
vector <ll> G, blocks;
bool ap[100000];
vector <ll> V, adj[100000], X[100000], E[200000];

void tar(ll u, ll p) {
  G.push_back(u);
  st[u] = low[u] = ++cnt;
  V.push_back(u);
  ll rch = 0;
  for (auto v : adj[u]) {
    if (!st[v]) {
      ++rch;
      tar(v, u);
      low[u] = min(low[u], low[v]);
      if (p != -1 && low[v] >= st[u]) ap[u] = 1;
      if (low[v] >= st[u]) {
        blocks.push_back(k);
        while (!V.empty()) {
          auto x = V.back();
          V.pop_back();
          X[x].push_back(k);
          ++sz[k];
          if (x == v) break;
        }
        X[u].push_back(k);
        ++sz[k];
        ++k;
      }
    }
    else if (v != p) {
      low[u] = min(low[u], st[v]);
    }
  }
  if (p == -1 && rch > 1) ap[u] = 1;
}

void calc(ll u, ll p) {
  //cout << u << '\n';
  if (u >= n) dp[u] = sz[u] - E[u].size();
  else dp[u] = 1;
  //cout << u << " " << dp[u] << '\n';
  for (auto v : E[u]) {
    if (v != p) {
      calc(v, u);
      dp[u] += dp[v];
      if (u >= n) {
        f += (dp[v]-1) * (G.size() - dp[v]); //down -> ap -> up
        f += (dp[v]-1) * (sz[u] - E[u].size()) * (G.size() - dp[v] - 1); //edge -> nonap -> any
        f += (sz[u] - E[u].size()) * (G.size() - dp[v] - 1); //ap -> nonap -> any
        if (p != -1 && sz[u] > 2) {
          f += (dp[v]-1) * (E[u].size()-1) * (sz[u] - 2) * 2; //down -> ap -> down
        }
      }
    }
  }
  for (auto v : E[u]) {
    if (v != p) {
      if (u >= n) {
        if (p != -1 && sz[u] > 2) {
          f += (dp[v]-1) * (dp[u]-sz[u]+1-(dp[v]-1)); //downL -> ap -> downR
        }
      }
    }
  }
  if (u >= n) {
    f += (G.size() - dp[u] - (p != -1)) * dp[u]; //up -> ap -> down
    if (p != -1 && sz[u] > 2) {
      f += (G.size() - dp[u] - 1) * (sz[u] - 1) * (E[u].size()-1) * 2; //up -> ap -> up
    }
    if (sz[u] > 2) {
      f += (sz[u]-1) * (sz[u]-2) * E[u].size(); //down -> ap -> down & up -> ap -> up
    }
    f += (G.size() - dp[u] - (p != -1)) * (sz[u] - E[u].size()) * (dp[u] - 1); //topedge -> nonap -> any
    if (p != -1) f += (sz[u] - E[u].size()) * (dp[u] - 1); //ap -> nonap -> any
    if (G.size() >= 2) {
      f += (sz[u] - E[u].size()) * (sz[u] - (ll)E[u].size() - 1) * (G.size() - 2); //nonap -> nonap -> any
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i=0; i<m; ++i) {
    cin >> a >> b;
    --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  k = n;
  for (int i=0; i<n; ++i) {
    if (!st[i]) {
      G.clear();
      blocks.clear();
      V.clear();
      tar(i, -1);
      for (auto u : G) {
        if (ap[u]) {
          for (auto v : X[u]) {
            E[u].push_back(v);
            E[v].push_back(u);
          }
        }
      }
      if (!blocks.empty()) calc(blocks[0], -1);
    }
  }
  cout << f << '\n';
}

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	12888 KB	Output is correct
2	Correct	5 ms	12892 KB	Output is correct
3	Correct	4 ms	12720 KB	Output is correct
4	Correct	4 ms	13044 KB	Output is correct
5	Correct	3 ms	12892 KB	Output is correct
6	Correct	3 ms	12888 KB	Output is correct
7	Incorrect	2 ms	12888 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	12888 KB	Output is correct
2	Correct	5 ms	12892 KB	Output is correct
3	Correct	4 ms	12720 KB	Output is correct
4	Correct	4 ms	13044 KB	Output is correct
5	Correct	3 ms	12892 KB	Output is correct
6	Correct	3 ms	12888 KB	Output is correct
7	Incorrect	2 ms	12888 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #3
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	81 ms	31164 KB	Output is correct
2	Correct	75 ms	31380 KB	Output is correct
3	Correct	98 ms	35624 KB	Output is correct
4	Correct	98 ms	31044 KB	Output is correct
5	Correct	95 ms	30916 KB	Output is correct
6	Correct	129 ms	36800 KB	Output is correct
7	Correct	113 ms	29904 KB	Output is correct
8	Correct	113 ms	33160 KB	Output is correct
9	Correct	121 ms	27728 KB	Output is correct
10	Correct	102 ms	28780 KB	Output is correct
11	Correct	72 ms	23400 KB	Output is correct
12	Correct	77 ms	23376 KB	Output is correct
13	Correct	65 ms	22868 KB	Output is correct
14	Correct	65 ms	22624 KB	Output is correct
15	Correct	49 ms	21052 KB	Output is correct
16	Correct	48 ms	20900 KB	Output is correct
17	Correct	4 ms	14424 KB	Output is correct
18	Correct	5 ms	14428 KB	Output is correct
19	Correct	5 ms	14428 KB	Output is correct
20	Correct	5 ms	14424 KB	Output is correct
21	Correct	4 ms	14428 KB	Output is correct
22	Correct	4 ms	14428 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	12888 KB	Output is correct
2	Correct	3 ms	12892 KB	Output is correct
3	Correct	4 ms	12892 KB	Output is correct
4	Correct	3 ms	13148 KB	Output is correct
5	Correct	4 ms	13148 KB	Output is correct
6	Correct	3 ms	13148 KB	Output is correct
7	Correct	5 ms	13148 KB	Output is correct
8	Correct	3 ms	13148 KB	Output is correct
9	Correct	3 ms	13148 KB	Output is correct
10	Correct	4 ms	12892 KB	Output is correct
11	Correct	3 ms	12892 KB	Output is correct
12	Correct	5 ms	12892 KB	Output is correct
13	Correct	3 ms	12892 KB	Output is correct
14	Correct	3 ms	12892 KB	Output is correct
15	Correct	3 ms	12932 KB	Output is correct
16	Correct	4 ms	12892 KB	Output is correct
17	Correct	3 ms	12892 KB	Output is correct
18	Correct	3 ms	12892 KB	Output is correct
19	Correct	4 ms	12892 KB	Output is correct
20	Correct	3 ms	12892 KB	Output is correct

Subtask #5
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	106 ms	30000 KB	Output is correct
2	Correct	105 ms	30192 KB	Output is correct
3	Correct	94 ms	30008 KB	Output is correct
4	Correct	95 ms	30172 KB	Output is correct
5	Correct	96 ms	30104 KB	Output is correct
6	Correct	141 ms	49084 KB	Output is correct
7	Correct	154 ms	37244 KB	Output is correct
8	Correct	106 ms	35380 KB	Output is correct
9	Correct	115 ms	33712 KB	Output is correct
10	Correct	103 ms	29504 KB	Output is correct
11	Correct	103 ms	30008 KB	Output is correct
12	Correct	103 ms	29000 KB	Output is correct
13	Correct	103 ms	28992 KB	Output is correct
14	Correct	89 ms	27280 KB	Output is correct
15	Correct	79 ms	25884 KB	Output is correct
16	Correct	47 ms	21588 KB	Output is correct
17	Correct	72 ms	29132 KB	Output is correct
18	Correct	71 ms	28984 KB	Output is correct
19	Correct	76 ms	29356 KB	Output is correct
20	Correct	77 ms	29200 KB	Output is correct

Subtask #6
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12888 KB	Output is correct
2	Correct	3 ms	13072 KB	Output is correct
3	Incorrect	3 ms	12984 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	91 ms	30192 KB	Output is correct
2	Correct	105 ms	30008 KB	Output is correct
3	Incorrect	130 ms	29476 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #8
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	12888 KB	Output is correct
2	Correct	5 ms	12892 KB	Output is correct
3	Correct	4 ms	12720 KB	Output is correct
4	Correct	4 ms	13044 KB	Output is correct
5	Correct	3 ms	12892 KB	Output is correct
6	Correct	3 ms	12888 KB	Output is correct
7	Incorrect	2 ms	12888 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	12888 KB	Output is correct
2	Correct	5 ms	12892 KB	Output is correct
3	Correct	4 ms	12720 KB	Output is correct
4	Correct	4 ms	13044 KB	Output is correct
5	Correct	3 ms	12892 KB	Output is correct
6	Correct	3 ms	12888 KB	Output is correct
7	Incorrect	2 ms	12888 KB	Output isn't correct
8	Halted	0 ms	0 KB	-

답안 #951448

Compilation message