oj.uz

Submission #54808

# Submission time Handle Problem Language Result Execution time Memory
54808 2018-07-05T06:58:01 Z 강태규(#1507) Pipes (CEOI15_pipes) C++11
10 / 100
 5000 ms 5296 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;
struct link {
    int x;
    link * nxt;
} db[200000];
int tp = 0;

link * edge[100001];

int par[100001];
int dep[100001];

int par1[100001];
int sz[100001];

int par2[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 (sz[x] < sz[y]) swap(x, y);
    par1[y] = x;
    sz[x] += sz[y];
    return 1;
}

int merge2(int x, int y) {
    x = find2(x);
    y = find2(y);
    if (x == y) return 0;
    par2[y] = x;
    return 1;
}

void dfs(int x, int p) {
    for (link * i = edge[x]; i; i = i->nxt) {
        if (i->x == p) continue;
        if (find2(i->x) != find2(x)) {
            par[find2(i->x)] = find2(x);
            dep[find2(i->x)] = dep[find2(x)] + 1;
        }
        dfs(i->x, x);
    }
}

void addEdge(int x, int t) {
    link * ls = db + tp++;
    ls->x = t;
    ls->nxt = edge[x];
    edge[x] = ls;
}

int main() {
    int m;
    scanf("%d%d", &n, &m);
    while (m--) {
        int u, v;
        scanf("%d%d", &u, &v);
        if (find1(u) != find1(v)) {
            if (sz[find1(u)] < sz[find1(v)]) swap(u, v);
            addEdge(u, v);
            addEdge(v, u);
            par[v] = u;
            dep[v] = dep[u] + 1;
            dfs(v, u);
            merge1(u, v);
        }
        else if (find2(u) != find2(v)) {
            u = find2(u);
            v = find2(v);
            while (u != v) {
                if (dep[u] < dep[v]) swap(u, v);
                merge2(v, u);
                u = find2(par[u]);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (link * j = edge[i]; j; j = j->nxt) {
            if (i < j->x) continue;
            if (find2(i) != find2(j->x)) printf("%d %d\n", i, j->x);
        }
    }
	return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:86: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:89: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Wrong number of edges

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 640 KB Output is correct
2 Incorrect 31 ms 640 KB Wrong number of edges

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 596 KB Output is correct
2 Incorrect 121 ms 512 KB Wrong number of edges

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 912 KB Output is correct
2 Incorrect 310 ms 888 KB Wrong number of edges

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3911 ms 1820 KB Output is correct
2 Correct 2104 ms 2264 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5084 ms 3960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5014 ms 4476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5073 ms 5188 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5087 ms 5296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5061 ms 5048 KB Time limit exceeded
2 Halted 0 ms 0 KB -