# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
153170 | 2019-09-12T16:25:44 Z | Mercenary | Pipes (CEOI15_pipes) | C++14 | 5000 ms | 13944 KB |
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/trie_policy.hpp> #define pb push_back #define mp make_pair #define taskname "A" using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef pair<int,int> ii; typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; const int maxn = 1e5 + 5; const int logn = log2(maxn) + 1; int n , m , nEdge = 0; int P[maxn][logn]; int lab[maxn] , h[maxn] , dp[maxn]; vector<int> adj[maxn]; bitset<6000000 + 5> checked; int FindLab(int u){ return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]); } void BuildLCA(int u , int par){ P[u][0] = par; for(int i = 1 ; i < logn && P[u][i - 1] ; ++i){ P[u][i] = P[P[u][i - 1]][i - 1]; } } void dfs(int u , int par){ for(int c : adj[u]){ if(par != c){ h[c] = h[u] + 1; BuildLCA(c , u); dfs(c , u); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); if(fopen(taskname".INP","r")){ freopen(taskname".INP", "r",stdin); freopen(taskname".OUT", "w",stdout); } fill_n(lab,maxn,-1); cin >> n >> m; for(int u , v , s , t , i = 1 ; i <= m ; ++i){ cin >> u >> v; s = FindLab(u); t = FindLab(v); if(s != t){ if(lab[s] > lab[t])swap(s , t) , swap(u , v); lab[s] += lab[t]; lab[t] = s; adj[u].pb(v); adj[v].pb(u); checked[i] = 1; } } for(int i = 1 ; i <= n ; ++i){ if(h[i] == 0){ h[i] = 1; dfs(i , 0); } } fill_n(lab,maxn,-1); rewind(stdin); cin >> n >> m; for(int u , v , s , t , i = 1 ; i <= m ; ++i){ cin >> u >> v; if(checked[i])continue; auto lca = [&](int &u , int &v){ if(h[u] < h[v])swap(u , v); for(int i = 0 ; i < logn && h[u] != h[v] ; ++i){ if((h[u] - h[v]) & (1 << i))u = P[u][i]; } if(u == v)return u; for(int i = logn - 1 ; i >= 0 ; --i){ if(P[u][i] != P[v][i])u = P[u][i] , v = P[v][i]; } return P[u][0]; }; dp[u]++;dp[v]++; dp[lca(u,v)] -= 2; } fill_n(h,maxn,0); for(int i = 1 ; i <= n ; ++i){ if(h[i] == 0){ h[i] = 1; function<void(int&,int&)> dfs = [&](int& u , int &par){ for(int v : adj[u]){ if(v != par){ h[v] = h[u] + 1; dfs(v , u); dp[u] += dp[v]; if(dp[v] == 0)cout << u << " " << v << '\n'; } } }; dfs(i , i); } } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 3576 KB | Output is correct |
2 | Correct | 5 ms | 3576 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 3960 KB | Output is correct |
2 | Correct | 12 ms | 4004 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 341 ms | 3824 KB | Output is correct |
2 | Correct | 337 ms | 3832 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 606 ms | 4432 KB | Output is correct |
2 | Correct | 703 ms | 4600 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1038 ms | 5920 KB | Output is correct |
2 | Correct | 866 ms | 6716 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1503 ms | 10600 KB | Output is correct |
2 | Correct | 1314 ms | 10616 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2426 ms | 11764 KB | Output is correct |
2 | Correct | 2205 ms | 11912 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3443 ms | 13752 KB | Output is correct |
2 | Correct | 3249 ms | 13888 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4270 ms | 13680 KB | Output is correct |
2 | Correct | 4043 ms | 13944 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 5017 ms | 13176 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |