Submission #1043458

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1043458	2024-08-04T09:45:33 Z	vjudge1	Duathlon (APIO18_duathlon)	C++17	23 / 100	739 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)
{
  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);

      cnt[v][2] += 2 *(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	9052 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	552 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	9052 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	552 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	47 ms	23244 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	9052 KB	Output is correct
2	Correct	1 ms	9052 KB	Output is correct
3	Correct	1 ms	9052 KB	Output is correct
4	Correct	2 ms	9052 KB	Output is correct
5	Correct	2 ms	9008 KB	Output is correct
6	Correct	2 ms	9052 KB	Output is correct
7	Correct	2 ms	9084 KB	Output is correct
8	Correct	2 ms	9052 KB	Output is correct
9	Correct	3 ms	9048 KB	Output is correct
10	Correct	2 ms	9048 KB	Output is correct
11	Correct	2 ms	9116 KB	Output is correct
12	Correct	2 ms	9052 KB	Output is correct
13	Correct	1 ms	9052 KB	Output is correct
14	Correct	2 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	9052 KB	Output is correct
18	Correct	1 ms	9052 KB	Output is correct
19	Correct	1 ms	9052 KB	Output is correct
20	Correct	1 ms	9052 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	17812 KB	Output is correct
2	Correct	65 ms	18512 KB	Output is correct
3	Correct	56 ms	18496 KB	Output is correct
4	Correct	61 ms	18504 KB	Output is correct
5	Correct	60 ms	18496 KB	Output is correct
6	Correct	73 ms	23376 KB	Output is correct
7	Correct	66 ms	21664 KB	Output is correct
8	Correct	77 ms	20816 KB	Output is correct
9	Correct	65 ms	19852 KB	Output is correct
10	Correct	57 ms	17564 KB	Output is correct
11	Correct	57 ms	17740 KB	Output is correct
12	Correct	56 ms	17448 KB	Output is correct
13	Correct	56 ms	17064 KB	Output is correct
14	Correct	59 ms	16600 KB	Output is correct
15	Correct	47 ms	16208 KB	Output is correct
16	Correct	29 ms	14416 KB	Output is correct
17	Correct	48 ms	18924 KB	Output is correct
18	Correct	46 ms	19064 KB	Output is correct
19	Correct	47 ms	19172 KB	Output is correct
20	Correct	46 ms	19028 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	562 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	57 ms	17996 KB	Output is correct
2	Correct	62 ms	18252 KB	Output is correct
3	Runtime error	739 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	9052 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	552 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	9052 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	552 ms	1048576 KB	Execution killed with signal 9
8	Halted	0 ms	0 KB	-

Submission #1043458

Compilation message