oj.uz

Submission #54829

# Submission time Handle Problem Language Result Execution time Memory
54829 2018-07-05T07:51:58 Z admin Pipes (CEOI15_pipes) C++14
100 / 100
 1701 ms 8596 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
 
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
 
int n;
vector<int> edge[100001];
 
int par[100001];
int dep[100001];
 
int par1[100001];
int sz1[100001];
 
int par2[100001];
int sz2[100001];
int gr[100001];
 
int find1(int x) {
    if (par1[x]) return par1[x] = find1(par1[x]);
    return x;
}
 
int find2(int x) {
    if (par2[x]) return par2[x] = find2(par2[x]);
    return x;
}
 
int merge1(int x, int y) {
    x = find1(x);
    y = find1(y);
    if (x == y) return 0;
    if (sz1[x] < sz1[y]) swap(x, y);
    par1[y] = x;
    sz1[x] += sz1[y];
    return 1;
}
 
int merge2(int x, int y) {
    x = find2(x);
    y = find2(y);
    if (x == y) return 0;
    gr[y] = gr[x];
    if (sz2[x] < sz2[y]) swap(x, y);
    par2[y] = x;
    sz2[x] += sz2[y];
    return 1;
}
 
void dfs(int x, int p) {
    for (int i : edge[x]) {
        if (i == p) continue;
        if (find2(i) != find2(x)) {
            par[gr[find2(i)]] = gr[find2(x)];
            dep[gr[find2(i)]] = dep[gr[find2(x)]] + 1;
        }
        dfs(i, x);
    }
}
 
int main() {
    int m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        sz1[i] = 1;
        sz2[i] = 1;
        gr[i] = i;
    }
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        if (find1(u) != find1(v)) {
            if (sz1[find1(u)] < sz1[find1(v)]) swap(u, v);
            edge[u].push_back(v);
            edge[v].push_back(u);
            par[gr[find2(v)]] = gr[find2(u)];
            dep[gr[find2(v)]] = dep[gr[find2(u)]] + 1;
            dfs(v, u);
            merge1(u, v);
        }
        else if (gr[find2(u)] != gr[find2(v)]) {
            u = gr[find2(u)];
            v = gr[find2(v)];
            while (u != v) {
                if (dep[u] < dep[v]) swap(u, v);
                merge2(v, u);
                u = gr[find2(par[u])];
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j : edge[i]) {
            if (i < j) continue;
            if (gr[find2(i)] != gr[find2(j)]) printf("%d %d\n", i, j);
        }
    }
	return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 3200 KB Output is correct
2 Correct 242 ms 3200 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 4036 KB Output is correct
2 Correct 293 ms 4472 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 6796 KB Output is correct
2 Correct 435 ms 6848 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 7436 KB Output is correct
2 Correct 714 ms 7364 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 949 ms 8516 KB Output is correct
2 Correct 917 ms 8488 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1252 ms 8556 KB Output is correct
2 Correct 1244 ms 8596 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1530 ms 8184 KB Output is correct
2 Correct 1701 ms 8568 KB Output is correct