| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 143155 |
2019-08-13T09:12:56 Z |
Ruxandra985 |
Pipes (CEOI15_pipes) |
C++14 |
|
1826 ms |
24804 KB |
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define DIMN 100005
using namespace std;
int fth[DIMN],fth2[DIMN],sum[DIMN];
vector <int> v[DIMN];
int lvl[DIMN];
bool f[DIMN];
int d[18][DIMN];
int logg[DIMN];
int elem;
int root (int nod){
int init = nod,aux;
while (fth[nod]>0){
nod = fth[nod];
}
while (fth[init]>0){ /// amortizare
aux = fth[init];
fth[init] = nod;
init = aux;
}
return nod;
}
int root2 (int nod){
int init = nod,aux;
while (fth2[nod]>0){
nod = fth2[nod];
}
while (fth2[init]>0){ /// amortizare
aux = fth2[init];
fth2[init] = nod;
init = aux;
}
return nod;
}
void dfs (int nod,int tata){
int i,vecin;
f[nod] = 1;
for (i=0;i<v[nod].size();i++){
vecin = v[nod][i];
if (vecin!=tata){
dfs(vecin , nod);
sum[nod]+=sum[vecin];
if (!sum[vecin]){
printf ("%d %d\n",nod,vecin);
}
}
}
}
void dfs_lca (int nod,int niv,int tt){
int i,vecin;
d[0][nod] = tt;
lvl[nod] = niv;
f[nod] = 1;
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (vecin!=tt){
dfs_lca(vecin,niv+1,nod);
}
}
}
int kth (int nod , int k){
while (k && nod!=0){
nod=d[logg[k]][nod];
k=k-(1<<logg[k]);
}
return nod;
}
int query (int x,int y){
int st,dr,mid;
if (lvl[x] < lvl[y])
swap(x,y);
if (lvl[x] > lvl[y])
x = kth( x , lvl[x] - lvl[y] );
st = 0;
dr = lvl[x]-1;
while (st <= dr){
mid = (st + dr)/2;
if (kth(x,mid) == kth(y,mid))
dr = mid - 1;
else st = mid + 1;
}
return kth(x,st);
}
int main()
{
// freopen ("a.in" , "r" , stdin);
int n,m,i,x,y,rx,ry;
scanf ("%d%d",&n,&m);
for (i=1;i<=n;i++)
fth[i] = fth2[i] = -1;
for (i=1;i<=m;i++){
scanf ("%d%d",&x,&y);
rx = root(x);
ry = root(y);
if (rx != ry){ /// sunt in cc diferite
v[x].push_back(y);
v[y].push_back(x); /// mai multi arbori
if (fth[rx] < fth[ry]){
fth[rx]+=fth[ry];
fth[ry] = rx;
}
else {
fth[ry]+=fth[rx];
fth[rx] = ry;
}
}
else {
rx = root2(x);
ry = root2(y);
if (rx!=ry){ /// unesti in fth2
if (fth2[rx] < fth2[ry]){
fth2[rx]+=fth2[ry];
fth2[ry] = rx;
}
else {
fth2[ry]+=fth2[rx];
fth2[rx] = ry;
}
}
}
}
/// faci lca cu stramosi ca sa economisesti memorie
for (i=1;i<=n;i++){
if (!f[i]){
dfs_lca (i,1,0);
}
}
memset ( f, 0 ,sizeof(f) );
for (i=2;i<=2*n;i++)
logg[i] = logg[i/2] + 1;
for (int powe=1;powe<=logg[n];powe++){
for (i=1;i <= n;i++){
d[powe][i] = d[powe-1][d[powe-1][i]];
}
}
for (i=1;i<=n;i++){ /// daca ai o muchie in fth2 , stergi din fth
if (fth2[i]>0){
int lca = query (i , fth2[i]);
sum[i]++;
sum[fth2[i]]++;
sum[lca]-=2;
}
}
for (i=1;i<=n;i++){
if (!f[i])
dfs(i,0);
}
return 0;
}
Compilation message
pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
pipes.cpp: In function 'void dfs_lca(int, int, int)':
pipes.cpp:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (i=0;i<v[nod].size();i++){
~^~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:93: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:97:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d",&x,&y);
~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2812 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
3320 KB |
Output is correct |
| 2 |
Correct |
9 ms |
3328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
146 ms |
3108 KB |
Output is correct |
| 2 |
Correct |
144 ms |
3164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
258 ms |
3864 KB |
Output is correct |
| 2 |
Correct |
300 ms |
3876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
413 ms |
5568 KB |
Output is correct |
| 2 |
Correct |
360 ms |
6212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
550 ms |
11128 KB |
Output is correct |
| 2 |
Incorrect |
487 ms |
11100 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
909 ms |
12276 KB |
Output is correct |
| 2 |
Correct |
850 ms |
12512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1132 ms |
14416 KB |
Output is correct |
| 2 |
Incorrect |
1086 ms |
14440 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1429 ms |
14428 KB |
Output is correct |
| 2 |
Incorrect |
1377 ms |
14440 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1742 ms |
13968 KB |
Output is correct |
| 2 |
Runtime error |
1826 ms |
24804 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
