| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 153172 | 2019-09-12T16:37:51 Z | Mercenary | Pipes (CEOI15_pipes) | C++14 | 4709 ms | 14888 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;
void Read(int & x){
char ch;
x = 0;
for(ch = getchar() ; ch > '9' && ch < '0' ; ch = getchar());
for( ; ch <= '9' && ch >= '0' ; ch = getchar())x = x * 10 + ch - '0';
}
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;
Read(n);Read(m);
for(int u , v , s , t , i = 1 ; i <= m ; ++i){
// cin >> u >> v;
Read(u);Read(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);
}
}
rewind(stdin);
// cin >> n >> m;
Read(n);Read(m);
for(int u , v , s , t , i = 1 ; i <= m ; ++i){
// cin >> u >> v;
Read(u);Read(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 | 3448 KB | Output is correct |
| 2 | Correct | 5 ms | 3576 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 11 ms | 3960 KB | Output is correct |
| 2 | Correct | 11 ms | 3960 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 280 ms | 3792 KB | Output is correct |
| 2 | Correct | 262 ms | 3804 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 532 ms | 4424 KB | Output is correct |
| 2 | Correct | 596 ms | 4476 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 916 ms | 5920 KB | Output is correct |
| 2 | Correct | 764 ms | 6824 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1302 ms | 10720 KB | Output is correct |
| 2 | Correct | 1130 ms | 10888 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2212 ms | 11696 KB | Output is correct |
| 2 | Correct | 1944 ms | 11904 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3039 ms | 13672 KB | Output is correct |
| 2 | Correct | 2785 ms | 13748 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3930 ms | 13672 KB | Output is correct |
| 2 | Correct | 3675 ms | 13752 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 4709 ms | 13140 KB | Output is correct |
| 2 | Correct | 4053 ms | 14888 KB | Output is correct |