Submission #858996

#	Time	Username	Problem	Language	Result	Execution time	Memory
858996		KaleemRazaSyed	Pipes (CEOI15_pipes)	C++17	50 / 100	1969 ms	48704 KiB

pipes

#include<cstdio>
#include<vector>

using namespace std;

const int N = 100010, 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 = -1)
{
  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); // 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);

  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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10