oj.uz

Submission #48061

# Submission time Handle Problem Language Result Execution time Memory
48061 2018-05-09T17:44:03 Z Extazy Pipes (CEOI15_pipes) C++17
100 / 100
 1479 ms 12136 KB 
#include <bits/stdc++.h>
#define endl '\n'
#define time akghahgahgkahjgaj

using namespace std;

const int N = 100007;

struct dsu {
  int n,parents[N];

  void initialize(int k) {
    n=k;
    for(int i=1;i<=n;i++) {
      parents[i]=i;
    }
  }

  int find(int x) {
    while(x!=parents[x]) {
      parents[x]=parents[parents[x]];
      x=parents[x];
    }
    return x;
  }
} uf1, uf2;

int n,m;
int time[N],low[N],current_time;
vector < int > v[N];

void dfs(int node, int from=-1) {
  low[node]=time[node]=++current_time;

  int i;

  for(i=0;i<(int)(v[node].size());i++) if(v[node][i]!=from) {
    if(time[v[node][i]]==0) {
      dfs(v[node][i],node);
      if(low[v[node][i]]>time[node]) if(uf2.find(node)!=uf2.find(v[node][i])) {
        printf("%d %d\n", node, v[node][i]);
      }
      low[node]=min(low[node],low[v[node][i]]);
    }
    else {
      low[node]=min(low[node],time[v[node][i]]);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int i,x,y,fx,fy;

  scanf("%d %d", &n, &m);

  uf1.initialize(n);
  uf2.initialize(n);

  for(i=1;i<=m;i++) {
    scanf("%d %d", &x, &y);

    fx=uf1.find(x);
    fy=uf1.find(y);

    if(fx!=fy) {
      if(rand()%2) swap(fx,fy);
      uf1.parents[fx]=fy;
      v[x].push_back(y);
      v[y].push_back(x);
    }
    else {
      fx=uf2.find(x);
      fy=uf2.find(y);

      if(fx!=fy) {
        if(rand()%2) swap(fx,fy);
        uf2.parents[fx]=fy;
        v[x].push_back(y);
        v[y].push_back(x);
      }
    }
  }

  for(i=1;i<=n;i++) if(time[i]==0) {
    dfs(i);
  }

  return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3072 KB Output is correct
2 Correct 8 ms 2944 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 3040 KB Output is correct
2 Correct 111 ms 2936 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 3596 KB Output is correct
2 Correct 232 ms 3320 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 4920 KB Output is correct
2 Correct 308 ms 4728 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 9340 KB Output is correct
2 Correct 415 ms 7124 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 10336 KB Output is correct
2 Correct 713 ms 8240 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 979 ms 12136 KB Output is correct
2 Correct 926 ms 8972 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1209 ms 12124 KB Output is correct
2 Correct 1192 ms 8808 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1479 ms 11560 KB Output is correct
2 Correct 1405 ms 9652 KB Output is correct