#include <stdio.h>
#include <fstream>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string.h>
std::vector<int> AdjList[100005];
int Vis[100005];
int p[100005];
int H[100005];
int* Pa;
int mark[100005];
int N;
std::queue<std::pair<int, int> > Q;
int UF(int u)
{
return (p[u] == 0)?u:(p[u] = UF(p[u]));
}
void dfs(int u, int pa, int h)
{
// printf("dfs u%d pa%d h%d\n", u, pa, h);
Vis[u] = 1;
H[u] = h;
*(Pa + u - 1) = pa;
int i, v, s = AdjList[u].size();
for (i = 0; i < s; i++)
{
v = AdjList[u][i];
if (v != pa)
dfs(v, u, h + 1);
}
}
int lgN;
int lca(int u, int v)
{
if (H[v] > H[u])
return lca(v, u);
int i;
if (H[u] > H[v])
{
for (i = lgN - 1; i >= 0; i--)
if (H[*(Pa + N*i + u - 1)] > H[v])
u = *(Pa + N*i + u - 1);
u = *(Pa + u - 1);
}
if (u == v)
return u;
for (i = lgN - 1; i >= 0; i--)
{
if (*(Pa + N*i + u - 1) != *(Pa + N*i + v - 1))
{
u = *(Pa + N*i + u - 1);
v = *(Pa + N*i + v - 1);
}
}
return *(Pa + u - 1);
}
void dfsMark(int u, int pa)
{
int i, v, s = AdjList[u].size();
Vis[u] = 0;
for (i = 0; i < s; i++)
{
v = AdjList[u][i];
if (v != pa)
{
dfsMark(v, u);
mark[u] += mark[v];
}
}
}
int main()
{
int M;
scanf("%d %d", &N, &M);
for (lgN = 0; (1 << lgN) <= N; lgN++);
int i, ii, j, u, v, pu, pv;
int cnt = 0;
for (ii = 0; ii < M && cnt < N - 1; ii++)
{
scanf("%d %d", &u, &v);
if ((pu = UF(u)) != (pv = UF(v)))
{
AdjList[u].push_back(v);
AdjList[v].push_back(u);
p[pu] = pv;
cnt++;
}
// else
// {
// Q.push({u, v});
// }
}
Pa = (int*) malloc(sizeof(int[lgN][N]));
// memset(Pa, lgN*N, 0);
// printf("hello\n");
for (i = 1; i <= N; i++)
if (!Vis[i])
dfs(i, 0, 0);
for (j = 1; j < lgN; j++)
{
for (i = 1; i <= N; i++)
{
u = *(Pa + (j - 1)*N + i - 1);
// printf("j%d i%d u%d\n", j, i, u);
if (u != 0)
{
*(Pa + j*N + i - 1) = *(Pa + (j - 1)*N + u - 1);
}
else
{
*(Pa + j*N + i - 1) = 0;
}
// printf("%d\n", *(Pa + j*N + i - 1));
// Pa[j][i] = Pa[j - 1][Pa[j - 1][i]];
}
}
// printf("hello\n");
// while (!Q.empty())
// {
// u = Q.front().first;
// v = Q.front().second;
// Q.pop();
// // printf("Q u%d v%d\n", u, v);
// mark[u]++;
// mark[v]++;
// // printf("lca %d\n", lca(u, v));
// mark[lca(u, v)] -= 2;
// }
// Q.~queue<std::pair<int, int> >();
FILE* in = stdin;
fseek(in, 0, SEEK_SET);
fscanf(in, "%d %d", &N, &M);
for (ii = 0; ii < M; ii++)
{
fscanf(in, "%d %d", &u, &v);
// printf("# u%d v%d\n", u, v);
mark[u]++;
mark[v]++;
// printf("lca %d\n", lca(u, v));
mark[lca(u, v)] -= 2;
}
for (i = 1; i <= N; i++)
if (Vis[i])
dfsMark(i, 0);
for (i = 1; i <= N; i++)
{
// printf("mark[%d] = %d\n", i, mark[i]);
if (mark[i] == 0 && *(Pa + i - 1) != 0)
printf("%d %d\n", i, *(Pa + i - 1));
}
}
Compilation message
pipes.cpp: In function 'int main()':
pipes.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:133:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(in, "%d %d", &N, &M);
~~~~~~^~~~~~~~~~~~~~~~~~~~~
pipes.cpp:136:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(in, "%d %d", &u, &v);
~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2688 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
3200 KB |
Wrong number of edges |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
224 ms |
2944 KB |
Output is correct |
| 2 |
Incorrect |
326 ms |
2936 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
584 ms |
3700 KB |
Output is correct |
| 2 |
Incorrect |
923 ms |
3696 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1167 ms |
5228 KB |
Output is correct |
| 2 |
Incorrect |
1194 ms |
5848 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2176 ms |
10660 KB |
Output is correct |
| 2 |
Incorrect |
2435 ms |
10636 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4155 ms |
11852 KB |
Output is correct |
| 2 |
Incorrect |
4058 ms |
11764 KB |
Wrong number of edges |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5045 ms |
13904 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5005 ms |
13964 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5094 ms |
13360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
