Submission #1043490

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1043490	2024-08-04T10:05:59 Z	vjudge1	Duathlon (APIO18_duathlon)	C++17	23 / 100	758 ms	1048576 KB

count_triplets

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	49 ms	22948 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-

Submission #1043490

Compilation message