This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5, M = 6e6 + 5, LG = 16;
int *g[N];
int dsu[N], deg[N], lvl[N], accm[N], far[LG][N];
bitset<M> edgs(0);
int n, m, lptr;
static int get_dsu(int nod) {
return (dsu[nod] ? (dsu[nod] = get_dsu(dsu[nod])) : nod); }
static bool join(int a, int b) {
a = get_dsu(a);
b = get_dsu(b);
if (a == b)
return false;
if (rand() % 2)
swap(a, b);
dsu[a] = b;
return true; }
static void dfs(int u, int pap = 0) {
far[0][u] = pap;
lvl[u] = lvl[pap] + 1;
for (int i = 0; i < deg[u]; ++i) {
int v = g[u][i];
if (v != pap)
dfs(v, u); } }
static void build_rmq() {
for (int lg = 1; lg < LG; ++lg)
for (int u = 1; u <= n; ++u)
far[lg][u] = far[lg - 1][far[lg - 1][u]]; }
static inline int getfar(int lg, int nod) {
if (lg < LG)
return far[lg][nod];
lg-= LG - 1;
for (int i = 0; i < (1 << lg); ++i)
nod = far[LG - 1][nod];
return nod; }
static int lca(int a, int b) {
if (lvl[a] < lvl[b])
swap(a, b);
for (int lg = 0; lg < 17; ++lg)
if ((lvl[a] - lvl[b]) & (1 << lg))
a = getfar(lg, a);
if (a == b)
return a;
for (int lg = 16; lg >= 0; --lg) {
int u = getfar(lg, a), v = getfar(lg, b);
if (u != v) {
a = u;
b = v; } }
return far[0][a]; }
static void answer(int nod, int pap = 0) {
for (int i = 0; i < deg[nod]; ++i) {
int v = g[nod][i];
if (v != pap) {
answer(v, nod);
accm[nod]+= accm[v]; } }
if (!accm[nod] && pap != 0)
cout << nod << ' ' << pap << '\n'; }
const int BMAX = 1 << 12;
char buff[BMAX];
int bp = BMAX;
static void reset() {
rewind(stdin);
bp = BMAX; }
static inline char nextch() {
if (bp == BMAX) {
fread(buff, 1, BMAX, stdin);
bp = 0; }
return buff[ bp++ ]; }
static inline void get(int &x) {
char ch;
do {
ch = nextch(); }
while (ch < '0' || '9' < ch);
x = 0;
while ('0' <= ch && ch <= '9') {
x = x * 10 + (ch - '0');
ch = nextch(); } }
int main() {
#ifdef HOME
freopen("pipes.in", "r", stdin);
freopen("pipes.out", "w", stdout);
#else
srand(time(NULL));
#endif
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
get(n), get(m);
for (int a, b, i = 0; i < m; ++i) {
get(a), get(b);
if (join(a, b)) {
edgs[i] = true;
++deg[a], ++deg[b]; } }
for (int i = 1; i <= n; ++i) {
g[i] = new int[deg[i]];
deg[i] = 0; }
reset();
get(n), get(m);
for (int a, b, i = 0; i < m; ++i) {
get(a), get(b);
if (edgs[i]) {
g[a][deg[a]++] = b;
g[b][deg[b]++] = a; } }
for (int i = 1; i <= n; ++i)
if (!lvl[i])
dfs(i);
reset();
build_rmq();
get(n), get(m);
for (int a, b, i = 0; i < m; ++i) {
get(a), get(b);
if (!edgs[i]) {
accm[a]+= 1, accm[b]+= 1;
accm[lca(a, b)]-= 2; } }
for (int i = 1; i <= n; ++i)
if (lvl[i] == 1)
answer(i);
return 0; }
Compilation message (stderr)
pipes.cpp: In function 'char nextch()':
pipes.cpp:81:8: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread(buff, 1, BMAX, stdin);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |