oj.uz

답안 #1043490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1043490 2024-08-04T10:05:59 Z vjudge1 철인 이종 경기 (APIO18_duathlon) C++17
23 / 100
 758 ms 1048576 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 100'000 + 10;
int n, m;
vector<int> G[N], T[N];
bool seen[N];
ll cnt[N][3];
int h[N], minh[N], par[N], sz[N];
bool bridge[N];
vector<pair<int,int> > edges;

int root(int x)
{
  if(par[x] == x) return x;
  return par[x] = root(par[x]);
}

void merge(int a, int b)
{
  // cerr << "merge : " << a << ' '  << b << endl;
  a = root(a), b = root(b);
  if(a == b) return;
  if(sz[a] > sz[b]) swap(a, b);
  par[a] = b;
  sz[b] += sz[a];
}

void dfs(int v, int p = 0)
{
  minh[v] = h[v] = h[p] + 1;
  seen[v] = true;
  for(int u : G[v])
    {
      if(u > v)
	edges.push_back({u, v});
      if(u == p) continue;
      if(seen[u])
	{
	  minh[v] = min(h[u], minh[v]);
	}
      else
	{
	  dfs(u, v);
	  if(minh[u] > h[v])
	    bridge[u] = bridge[v] = true;
	  minh[v] = min(minh[u], minh[v]);
	}
    }
}

void compute(int v, int p = 0)
{
  cnt[v][0] = sz[v];
  cnt[v][1] = (sz[v] * (sz[v] - 1));
  cnt[v][2] = (sz[v] * (sz[v] - 1) * (sz[v] - 2));
  for(int u : T[v])
    {
      if(u == p) continue;
      compute(u, v);
      if(bridge[u] && bridge[v])
	cnt[v][2] += 2 * (cnt[v][1] * cnt[u][0] + cnt[v][0] * cnt[u][1]) + cnt[u][2];
      else
	cnt[v][2] += 3 * (cnt[v][1] * cnt[u][0] + cnt[v][0] * cnt[u][1]) + cnt[u][2];
      cnt[v][1] += cnt[u][1] + cnt[u][0];
      cnt[v][0] += cnt[u][0];
    }
  // cerr << v << ' ' << cnt[v][0] << ' ' << cnt[v][1] << ' ' << cnt[v][2] << ' ' << sz[v] << endl;
}

ll solve(int v)
{
  dfs(v);
  vector<pair<int,int> > tree;
  for(auto [x, y] : edges)
    {
      if(!bridge[x] && !bridge[y])
	merge(x, y);
      else
	tree.push_back({x, y});
    }
  
  edges.clear();
  for(auto& [x, y] : tree)
    {
      x = root(x);
      y = root(y);
      if(x > y) swap(x, y);
      edges.push_back({x, y});
    }
  sort(edges.begin(), edges.end());
  edges.resize(unique(edges.begin(), edges.end()) - edges.begin());
  for(auto [x, y] : edges)
    {
      T[x].push_back(y);
      T[y].push_back(x);
      // cerr << x << ' ' << y << endl;
    }
  edges.clear();
  compute(root(v));
  return cnt[root(v)][2];
}

int main()
{
  cin >> n >> m;
  for(int i = 0; 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 ++)
    par[i] = i, sz[i] = 1;
  
  ll ways = 0;
  for(int i = 1; i < n; i ++)
    {
      if(seen[i]) continue;
      ways += solve(i);
    }
  cout << ways << endl;
  
  return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Correct 1 ms 9052 KB Output is correct
4 Correct 1 ms 9052 KB Output is correct
5 Correct 1 ms 9052 KB Output is correct
6 Correct 1 ms 9052 KB Output is correct
7 Runtime error 547 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Correct 1 ms 9052 KB Output is correct
4 Correct 1 ms 9052 KB Output is correct
5 Correct 1 ms 9052 KB Output is correct
6 Correct 1 ms 9052 KB Output is correct
7 Runtime error 547 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 49 ms 22948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 17748 KB Output is correct
2 Correct 63 ms 17272 KB Output is correct
3 Correct 57 ms 17228 KB Output is correct
4 Correct 58 ms 17036 KB Output is correct
5 Correct 67 ms 17268 KB Output is correct
6 Correct 60 ms 22100 KB Output is correct
7 Correct 60 ms 20340 KB Output is correct
8 Correct 59 ms 19540 KB Output is correct
9 Correct 59 ms 18760 KB Output is correct
10 Correct 59 ms 16284 KB Output is correct
11 Correct 74 ms 16488 KB Output is correct
12 Correct 68 ms 15980 KB Output is correct
13 Correct 55 ms 15876 KB Output is correct
14 Correct 47 ms 15444 KB Output is correct
15 Correct 48 ms 15116 KB Output is correct
16 Correct 27 ms 13916 KB Output is correct
17 Correct 49 ms 17820 KB Output is correct
18 Correct 46 ms 17732 KB Output is correct
19 Correct 52 ms 17728 KB Output is correct
20 Correct 47 ms 17748 KB Output is correct

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 9052 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Runtime error 591 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 17668 KB Output is correct
2 Correct 58 ms 16972 KB Output is correct
3 Runtime error 758 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Correct 1 ms 9052 KB Output is correct
4 Correct 1 ms 9052 KB Output is correct
5 Correct 1 ms 9052 KB Output is correct
6 Correct 1 ms 9052 KB Output is correct
7 Runtime error 547 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 9048 KB Output is correct
2 Correct 1 ms 9052 KB Output is correct
3 Correct 1 ms 9052 KB Output is correct
4 Correct 1 ms 9052 KB Output is correct
5 Correct 1 ms 9052 KB Output is correct
6 Correct 1 ms 9052 KB Output is correct
7 Runtime error 547 ms 1048576 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -