oj.uz

Submission #859010

# Submission time Handle Problem Language Result Execution time Memory
859010 2023-10-09T14:20:05 Z KaleemRazaSyed Pipes (CEOI15_pipes) C++17
100 / 100
 2071 ms 14600 KB 
#include<cstdio>
#include<vector>

using namespace std;

const int N = 100001, K = 18;
int par[N][K]; // par[v][k] = parent at level 2^k above v
int cycle[N]; // cycle[i] = count of the #cycle in which edge i ---> par[i][0] is used
int sz[N]; // sz[i] = size of the component whose root is i
int dsuPar[N]; // dsuPar[i] = parent in dsu 
int h[N]; // h[i] = dis(i, root) where {i, root} are in same component 
vector<int> G[N];

void dfs_cycle(int &v, int &p)
{
  for(int u : G[v])
    if(u != p)
      {
	dfs_cycle(u, v);
	cycle[v] += cycle[u];
      }
}

int root(int &v)
{
  if(dsuPar[v] == 0) return v;
  return dsuPar[v] = root(dsuPar[v]);
}

int lca(int a, int b)
{
  if(h[b] > h[a])
    swap(a, b);
  for(int i = 0; i < K; i++)
    if((1<<i) & (h[a] - h[b]))
      a = par[a][i];

  if(a == b)
    return a;

  for(int i = K-1; i >= 0; i--)
    if(par[a][i] != par[b][i])
      a = par[a][i], b = par[b][i];

  return par[a][0];
}

void dfs_reverse_cycle(int &v, int &p)
{
  h[v] = h[p] + 1;
  par[v][0] = p;
  for(int k = 1; k < K; k++)
    par[v][k] = par[par[v][k-1]][k-1];

  for(int u : G[v])
    if(u != p)
      {
	cycle[v] -= cycle[u];
	dfs_reverse_cycle(u, v);
      }
}

void merge(int &u, int &v)
{
  int ru = root(u), rv = root(v);
  if(rv == ru)
    {
      cycle[v]++;
      cycle[u]++;
      cycle[lca(u, v)] -= 2;
      return;
    }

  if(sz[ru] > sz[rv])
    swap(ru, rv), swap(u, v);

  // ru have on the smaller size of component
  dfs_cycle(ru, ru); // find the cycle values of ru component
  // update the path of a -> par[a][0] -> par[par[a][0]][0] -> .... -> ru

  vector<int> path = {u};
  while(par[path.back()][0]!=0)
    path.push_back(par[path.back()][0]);

  for(int i = path.size() - 1; i > 0; i--)
    cycle[path[i]] = cycle[path[i-1]];
  cycle[path[0]] = 0;

  dfs_reverse_cycle(u, v);

  G[u].push_back(v);
  G[v].push_back(u);
  
  dsuPar[ru] = rv; 
  sz[rv] += sz[ru]; 
  
}

int main()
{
  int n, m;
  scanf("%d %d",&n, &m);

  for(int i = 1; i <= n; i++)
    sz[i] = 1;
  
  for(int i = 0; i < m; i++)
    {
      int u, v;
      scanf("%d %d", &u, &v);
      merge(u, v);
    }

  for(int i = 1; i <= n; i++)
    if(par[i][0]==0)
      dfs_cycle(i, i);

  for(int i = 1; i <= n; i++)
    if(cycle[i] == 0 and par[i][0]!=0)
      printf("%d %d\n", i, par[i][0]);
  return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   scanf("%d %d",&n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:110:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |       scanf("%d %d", &u, &v);
      |       ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5464 KB Output is correct
2 Correct 1 ms 5468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5468 KB Output is correct
2 Correct 5 ms 5468 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 5468 KB Output is correct
2 Correct 138 ms 5640 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 5840 KB Output is correct
2 Correct 293 ms 5832 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 435 ms 6744 KB Output is correct
2 Correct 365 ms 7204 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 11432 KB Output is correct
2 Correct 512 ms 11348 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 927 ms 12492 KB Output is correct
2 Correct 897 ms 12352 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1258 ms 14416 KB Output is correct
2 Correct 1198 ms 14388 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1656 ms 14392 KB Output is correct
2 Correct 1799 ms 14444 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2071 ms 13884 KB Output is correct
2 Correct 1891 ms 14600 KB Output is correct