# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1028129 | 2024-07-19T14:09:25 Z | qwewq | Pipes (CEOI15_pipes) | C++14 | 729 ms | 13204 KB |
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5; vector < int > adj[N + 2]; struct dsu{ int par[N + 2]; int find_par(const int &u){ if(par[u] < 0)return u; par[u] = find_par(par[u]); return par[u]; } bool union_set(int u , int v){ u = find_par(u); v = find_par(v); if(u != v){ if(par[u] > par[v])swap(u , v); par[u] += par[v]; par[v] = u; return true; } return false; } } par1 , par2; int timer = 0; int n , m; void dfs(int c, int depth, int par){ par1.par[c] = depth; par2.par[c] = par1.par[c]; int op = par; for (int i : adj[c]){ if (i == par){ continue;} if (par1.par[i] != -1){ par2.par[c] = min( par2.par[c] ,par1.par[i]); continue;} dfs(i,depth+1,c); par2.par[c] = min(par2.par[c] , par2.par[i]); } if (par2.par[c] >= depth && op != -1) cout << c << " " << op << '\n'; } void solve() { cin >> n >> m; for(int i = 1; i <= n; i++){ par1.par[i] = par2.par[i] = -1; } for(int i = 1; i <= m ;i ++){ int u , v; cin >> u >> v; if(par1.union_set(u , v)){ adj[u].push_back(v); adj[v].push_back(u); // cout << u << ' ' << v<< '\n'; } else if(par2.union_set(u , v)){ adj[u].push_back(v); adj[v].push_back(u); // cout << u << ' '<< v << '\n'; } } for(int i = 1; i <= n ; i ++){ par1.par[i] = par2.par[i] = -1; } for(int i = 1; i <= n ; i++){ if(par1.par[i] == -1)dfs(i , 0 , -1); } } signed main() { ios::sync_with_stdio(0), cin.tie(0); #define _ "maxseq." if (fopen(_ "inp", "r")) { freopen(_ "inp", "r", stdin); freopen(_ "out", "w", stdout); } solve(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2652 KB | Output is correct |
2 | Incorrect | 1 ms | 2652 KB | Wrong number of edges |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 3164 KB | Output is correct |
2 | Incorrect | 3 ms | 2904 KB | Wrong number of edges |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 55 ms | 2980 KB | Output is correct |
2 | Incorrect | 61 ms | 2904 KB | Wrong number of edges |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 93 ms | 3784 KB | Wrong number of edges |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 156 ms | 5204 KB | Output is correct |
2 | Correct | 134 ms | 4944 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 213 ms | 10012 KB | Output is correct |
2 | Incorrect | 186 ms | 6668 KB | Wrong number of edges |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 367 ms | 11280 KB | Output is correct |
2 | Incorrect | 321 ms | 8356 KB | Wrong number of edges |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 443 ms | 13204 KB | Output is correct |
2 | Incorrect | 497 ms | 8272 KB | Wrong number of edges |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 558 ms | 13088 KB | Output is correct |
2 | Incorrect | 628 ms | 8272 KB | Wrong number of edges |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 729 ms | 12696 KB | Output is correct |
2 | Correct | 649 ms | 9812 KB | Output is correct |