Submission #311620

#	Time	Username	Problem	Language	Result	Execution time	Memory
311620		ly20	Pipes (CEOI15_pipes)	C++17	40 / 100	1862 ms	27084 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 112345;
vector <int> grafo[MAXN], id[MAXN];
int pai[MAXN], tam[MAXN], pai2[MAXN], tam2[MAXN];
vector <pair <int, int> > ar;
int low[MAXN], prof[MAXN], t, tp[MAXN];
vector <int> resp;
int find(int v) {
    if(v == pai[v]) return v;
    return pai[v] = find(pai[v]);
}
int find2(int v) {
    if(v == pai2[v]) return v;
    return pai2[v] = find2(pai2[v]);
}
void une(int a, int b) {
    a = find(a); b = find(b);
    if(a == b) return;
    if(tam[a] > tam[b]) {
        pai[b] = a;
        tam[a] += tam[b];
    }
    else {
        pai[a] = b;
        tam[b] += tam[a];
    }
}
void une2(int a, int b) {
    a = find2(a); b = find2(b);
    if(a == b) return;
    if(tam2[a] > tam2[b]) {
        pai2[b] = a;
        tam2[a] += tam2[b];
    }
    else {
        pai2[a] = b;
        tam2[b] += tam2[a];
    }
}
void dfs(int v, int p) {
    tp[v] = ++t;
    low[v] = tp[v];
    for(int i = 0; i < grafo[v].size(); i++) {
        int viz = grafo[v][i], at = id[v][i];
        if(at == p) continue;
        if(tp[viz] != 0) {
            low[v] = min(low[v], tp[viz]);
        }
        else {
            dfs(viz, at);
            low[v] = min(low[v], low[viz]);
            if(low[viz] > tp[v]) {
                resp.push_back(at);
            }
        }
    }
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) {
        pai[i] = i; tam[i] = 1; pai2[i] = i; tam2[i] = 1;
    }
    for(int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        if(find(a) == find(b)) {
            une2(a, b);
            continue;
        }
        une(a, b);
        ar.push_back(make_pair(a, b));
    }
    //printf("\n\n");
    for(int i = 0; i < ar.size(); i++) {
        int a = find2(ar[i].first), b = find2(ar[i].second);
        if(a == b) continue;
        grafo[a].push_back(b); grafo[b].push_back(a);
        id[a].push_back(i); id[b].push_back(i);
        //printf("%d %d\n", ar[i].first, ar[i].second);
        //printf("%d %d\n", a, b);
    }
    //printf("\n\n");
    for(int i = 1; i <= n; i++) {
        if(tp[i] == 0) dfs(i, -1);
    }
    for(int i = 0; i < resp.size(); i++) printf("%d %d\n", ar[resp[i]].first, ar[resp[i]].second);
    return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i = 0; i < grafo[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0; i < ar.size(); i++) {
      |                    ~~^~~~~~~~~~~
pipes.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i = 0; i < resp.size(); i++) printf("%d %d\n", ar[resp[i]].first, ar[resp[i]].second);
      |                    ~~^~~~~~~~~~~~~
pipes.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10