| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 143140 |
2019-08-13T08:37:01 Z |
Ruxandra985 |
Pipes (CEOI15_pipes) |
C++14 |
|
1708 ms |
29516 KB |
#include <cstdio>
#include <vector>
#include <algorithm>
#define DIMN 100005
using namespace std;
int fth[DIMN],fth2[DIMN],sum[DIMN];
vector <int> v[DIMN];
int eul[5*DIMN],nv[5*DIMN],first[DIMN],f[DIMN];
int d[20][5*DIMN];
int logg[5*DIMN];
int elem;
//freopen ("a.in" , "r" , stdin);
//freopen ("a.out" , "w" , stdout);
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;
eul[++elem]=nod;
nv[elem] = niv;
first[nod] = elem; /// prima poz;
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (vecin!=tt){
dfs_lca(vecin,niv+1,nod);
eul[++elem]=nod;
nv[elem]=niv;
}
}
}
int query (int x,int y){
int px,py,len;
px=first[x];
py=first[y];
/// minimul din intervalul px py
/// in d e pozitia din eul unde e nivelul minim
if (px>py)
swap(px,py);
len = py-px+1;
if (nv[ d[logg[len]][px] ] < nv[ d[logg[len]][py-(1<<logg[len])+1] ])
return d[logg[len]][px];
return d[logg[len]][py-(1<<logg[len])+1];
}
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 din arborele v
for (i=1;i<=n;i++){
if (!first[i])
dfs_lca (i,0,0);
}
for (i=2;i<=2*n;i++)
logg[i] = logg[i/2] + 1;
for (i=1;i<=elem;i++){
d[0][i] = i;
}
for (int powe=1;powe<=logg[elem];powe++){
for (i=1;i + (1<<powe)-1 <=elem;i++){
if (nv[d[powe-1][i]] < nv[d[powe-1][i + (1<<(powe-1))]])
d[powe][i] = d[powe-1][i];
else d[powe][i] = d[powe-1][i + (1<<(powe-1))];
}
}
for (i=1;i<=n;i++){ /// daca ai o muchie in fth2 , stergi din fth
if (fth2[i]>0){
int lca = eul[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:83: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:87: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 |
2808 KB |
Output is correct |
| 2 |
Correct |
4 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
3580 KB |
Output is correct |
| 2 |
Correct |
9 ms |
3576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
3400 KB |
Output is correct |
| 2 |
Correct |
140 ms |
3320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
245 ms |
4500 KB |
Output is correct |
| 2 |
Correct |
288 ms |
4520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
402 ms |
7416 KB |
Output is correct |
| 2 |
Correct |
347 ms |
8568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
554 ms |
16860 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
864 ms |
19056 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1120 ms |
22992 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1381 ms |
22996 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1708 ms |
29516 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 2 |
Halted |
0 ms |
0 KB |
- |
