oj.uz

답안 #125434

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125434 2019-07-05T09:51:46 Z eriksuenderhauf Pipes (CEOI15_pipes) C++11
100 / 100
 1722 ms 12156 KB 
    //#pragma GCC optimize("O3")
    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #include <ext/rope>
    #define mem(a,v) memset((a), (v), sizeof (a))
    #define enl printf("\n")
    #define case(t) printf("Case #%d: ", (t))
    #define ni(n) scanf("%d", &(n))
    #define nl(n) scanf("%I64d", &(n))
    #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
    #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
    #define pri(n) printf("%d\n", (n))
    #define prl(n) printf("%I64d\n", (n))
    #define pii pair<int, int>
    #define pil pair<int, long long>
    #define pll pair<long long, long long>
    #define vii vector<pii>
    #define vil vector<pil>
    #define vll vector<pll>
    #define vi vector<int>
    #define vl vector<long long>
    #define pb push_back
    #define mp make_pair
    #define fi first
    #define se second
    using namespace std;
    using namespace __gnu_pbds;
    typedef long long ll;
    typedef cc_hash_table<int,int,hash<int>> ht;
    typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
    const double pi = acos(-1);
    const int MOD = 1e9 + 7;
    const int INF = 1e9 + 7;
    const int MAXN = 1e5 + 5;
    const double eps = 1e-9;
    vi adj[MAXN];
    int cnt = 1, par[MAXN], par2[MAXN], lo[MAXN];
     
    int qry(int x) { return x == par[x] ? x : par[x] = qry(par[x]); }
    void join(int u, int v) { u = qry(u), v = qry(v); par[u] = v; }
     
    int qry2(int x) { return x == par2[x] ? x : par2[x] = qry2(par2[x]); }
    void join2(int u, int v) { u = qry2(u), v = qry2(v); par2[u] = v; }
     
    void dfs(int u, int p) {
    	par[u] = lo[u] = cnt++;
    	while (!adj[u].empty()) {
    		int v = adj[u].back();
    		adj[u].pop_back();
    		if (!par[v]) {
    			dfs(v, u);
    			lo[u] = min(lo[u], lo[v]);
    			if (lo[v] > par[u] && qry2(u) != qry2(v))
    				printf("%d %d\n", u, v);
    		} else if (v != p)
    			lo[u] = min(lo[u], par[v]);
    	}
    }
     
    int main() {
    	int n, m;
    	scanf("%d %d", &n, &m);
    	for (int i = 1; i <= n; i++)
    		par[i] = par2[i] = i;
    	for (int i = 0; i < m; i++) {
    		int u, v; scanf("%d %d", &u, &v);
    		if (qry2(u) == qry2(v))
    			continue;
    		if (qry(u) == qry(v)) {
    			adj[u].pb(v);
    			adj[v].pb(u);
    			join2(u, v);
    			continue;
    		}
    		join(u, v);
    		adj[u].pb(v);
    		adj[v].pb(u);
    	}
    	for (int i = 1; i <= n; i++)
    		par[i] = lo[i] = 0;
    	for (int i = 1; i <= n; i++)
    		if (!par[i])
    			dfs(i, 0);
        return 0;
    }

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 3064 KB Output is correct
2 Correct 9 ms 2936 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 139 ms 3020 KB Output is correct
2 Correct 137 ms 2936 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 3580 KB Output is correct
2 Correct 282 ms 3220 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 399 ms 4856 KB Output is correct
2 Correct 346 ms 4700 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 559 ms 9336 KB Output is correct
2 Correct 495 ms 6904 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 863 ms 10340 KB Output is correct
2 Correct 818 ms 8152 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1156 ms 12148 KB Output is correct
2 Correct 1079 ms 8416 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1397 ms 12156 KB Output is correct
2 Correct 1319 ms 8568 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1722 ms 11600 KB Output is correct
2 Correct 1613 ms 9548 KB Output is correct