oj.uz

답안 #116707

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116707 2019-06-13T15:44:15 Z JohnTitor Pipes (CEOI15_pipes) C++11
60 / 100
 705 ms 27308 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Pipes"
class dsu{
public:
    int n;
    int r[100001];
    vector <pair <int, int>> edges;
    void reset(int n){
        this->n=n;
        FOR(i, 1, n) r[i]=-1;
        edges.clear();
    }
    int root(int u){
        if(r[u]<0) return u;
        return r[u]=root(r[u]);
    }
    bool unite(int u, int v){
        int ou=u;
        int ov=v;
        u=root(u);
        v=root(v);
        if(u==v) return 0;
        edges.pb(mp(ou, ov));
        if(r[u]>r[v]) swap(u, v);
        r[u]+=r[v];
        r[v]=u;
        return 1;
    }
    bool connected(int u, int v){
        return root(u)==root(v);
    }
} d[2];
int n, m;
vector <int> g[100001];
bool done[100001];
int cnt=0;
int low[100001];
int num[100001];
int p[100001];
void dfs(int u){
    done[u]=1;
    cnt++;
    num[u]=low[u]=cnt;
    for(auto &x: g[u]) if(x==p[u]){
        swap(x, g[u].back());
        g[u].pop_back();
        break;
    }
    for(int v: g[u]) if(!done[v]){
        p[v]=u;
        dfs(v);
        low[u]=min(low[u], low[v]);
    }
    else low[u]=min(low[u], num[v]);
    for(int v: g[u]) if(p[v]==u){
        if(low[v]>num[u]){
            write(u);
            putchar(' ');
            writeln(v);
        }
        p[v]=0;
    }
}

int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(n);
    read(m);
    d[0].reset(n);
    d[1].reset(n);
    {
        int u, v;
        FOR(i, 1, m){
            read(u);
            read(v);
            if(!d[0].unite(u, v)) d[1].unite(u, v);
        }
    }
    FOR(b, 0, 1){
        while(!d[b].edges.empty()){
            auto p=d[b].edges.back();
            d[b].edges.pop_back();
            g[p.first].pb(p.second);
            g[p.second].pb(p.first);
        }
    }
    FOR(i, 1, n) if(!done[i]) dfs(i);
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 5 ms 2688 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3456 KB Output is correct
2 Correct 7 ms 3200 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 3816 KB Output is correct
2 Correct 51 ms 3604 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 4560 KB Output is correct
2 Correct 103 ms 4212 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 6672 KB Output is correct
2 Correct 134 ms 6528 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 12596 KB Output is correct
2 Runtime error 269 ms 27064 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 361 ms 14552 KB Output is correct
2 Correct 326 ms 10992 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 566 ms 16556 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 592 ms 17128 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 705 ms 16024 KB Output is correct
2 Runtime error 681 ms 27308 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)