pipes.cpp: In member function 'void LinkCutTree::pathUpdate(int, int, bool)':
pipes.cpp:62:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(x != z) carry[x] = 1; if(y != z) carry[y] = 1;
^~
pipes.cpp:62:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(x != z) carry[x] = 1; if(y != z) carry[y] = 1;
^~
pipes.cpp: In function 'void deal()':
pipes.cpp:7:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fori(v) for(int i=0; i<v; i++)
~^~~~~~~~~
#define forj(v) for(int j=0; j<v; j++)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#define fork(v) for(int k=0; k<v; k++)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#define forl(v) for(int l=0; l<v; l++)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#define fort(v) for(int t=0; t<v; t++)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#define forz(v) for(int z=0; z<v; z++)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#define ll long long int
~~~~~~~~~~~~~~~~~~~~~~~~~
#define double long double
~~~~~~~~~~~~~~~~~~~~~~~~~~~
#define MAX (int)(pow(10,5)+ 10)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#define pb(a) push_back(a)
~~~~~~~~~~~~~~~~~~~~~~~~~~~
// #define cout out
~~~~~~~~~~~~~~~~~~~~
// #define cin in
~~~~~~~~~~~~~~~~~~
ll inf = pow(10,9);
~~~~~~~~~~~~~~~~~~~~
ll modulo = inf;
~~~~~~~~~~~~~~~~~
double eps = 1e-10;
~~~~~~~~~~~~~~~~~~~~
ifstream in;
~~~~~~~~~~~~~
ofstream out;
~~~~~~~~~~~~~~
//*/
~~~~~
////////////////////////////////////////////////////////////////////////////////
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Link-cut tree: O(lg n) for all ops, TESTED (DYNALCA, DYNACON1, and more)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
////////////////////////////////////////////////////////////////////////////////
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// link(p, q) - makes the *root* p a child of the node q. if p is not a root,
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// makeroot will be called and lca(p, q) will be changed.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// cut(p) - deletes the edge connecting p to its parent
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// cut(p, q) - delete the edge connecting p to q (or on the path from p to q)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// pathAggregate(p, q) - returns the sum of weights on the path from p to q.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// this operation can be min, adding a constant, etc.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// pathUpdate(p, q) - increase value of all nodes between x and y inc. by c.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// lca(p, q) - returns lca of nodes p and q.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// findroot(p) - returns the root of node p's tree
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// makeroot(p) - makes p the root of its tree
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
struct LinkCutTree { vector<int> l,r,p,pp,flip; int null;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
vector<bool> sum, carry, val;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void init(int n) {
~~~~~~~~~~~~~~~~~~~
vector<int>* v[] = {&l, &r, &p, &pp, &flip};
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int ival[] = {null=n, null, null, null, 0};
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sum.clear(), carry.clear(), val.clear();
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sum.resize(n+1, 0), carry.resize(n+1, 0), val.resize(n+1, 0);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
for (int i = 0; i < 5; i++) { v[i]->clear(); v[i]->resize(n+1, ival[i]); }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
}
~~
inline int access(int x) {
~~~~~~~~~~~~~~~~~~~~~~~~~~~
if(r[splay(x)] != null) r[pp[r[x]] = x] = p[r[x]] = null;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
for(int w=x; update(w)>=0 && splay(w=pp[x]) != null; splay(r[p[x]=w]=x))
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
if(r[w] != null) p[r[pp[r[w]]=w]] = null;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
return x; }
~~~~~~~~~~~~
void makeroot(int x) { access(x); flip[x] ^= 1; push(x); }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int findroot(int x) {
~~~~~~~~~~~~~~~~~~~~~~
for(access(x); l[x] != null; x = l[x]) {}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
return access(x); }
~~~~~~~~~~~~~~~~~~~~
int pathAggregate(int x) { return sum[access(x)]; }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int pathAggregate(int x, int y) { makeroot(x); return pathAggregate(y); }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void cut(int x) { l[x] = p[l[access(x)]] = null; }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void cut(int x, int y) { makeroot(y); cut(x); }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void link(int x, int y) { makeroot(x); l[p[access(y)]=access(x)] = y; }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void pathUpdate(int x, int y, bool c) { int z = lca(x,y);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
if(x != z) carry[x] = 1; if(y != z) carry[y] = 1;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
val[z] = 1; }
~~~~~~~~~~~~~~
inline int splay(int x) {
~~~~~~~~~~~~~~~~~~~~~~~~~~
for(push(x); p[x] != null; lift(x))
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
if(l[l[p[p[x]]]] == x || r[r[p[p[x]]]] == x) lift(p[x]);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
else lift(x);
~~~~~~~~~~~~~~
return x; }
~~~~~~~~~~~~
void push(int x) {
~~~~~~~~~~~~~~~~~~~
if(flip[x]==1) {
~~~~~~~~~~~~~~~~~
swap(l[x], r[x]);
~~~~~~~~~~~~~~~~~~
flip[x]^=1; flip[l[x]]^=1; flip[r[x]]^=1; }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
if(carry[x])
~~~~~~~~~~~~~
carry[l[x]] = 1, carry[r[x]] = 1, val[x] = 1;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
carry[x] = 0; }
~~~~~~~~~~~~~~~~
int update(int x) {
~~~~~~~~~~~~~~~~~~~~
if(x == null) return x;
~~~~~~~~~~~~~~~~~~~~~~~~
sum[x] = (val[x] || sum[l[x]] || sum[r[x]] || carry[x]);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
return x; }
~~~~~~~~~~~~
int lca(int x, int y) {
~~~~~~~~~~~~~~~~~~~~~~~~
access(x); access(y); splay(x);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
return access(pp[x]==null?x:pp[x]); }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
void lift(int x) {
~~~~~~~~~~~~~~~~~~~
if(p[x] == null) return;
~~~~~~~~~~~~~~~~~~~~~~~~~
push(p[x]); push(x); push(l[x]); push(r[x]);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pp[x] = pp[p[x]]; pp[p[x]] = null;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
int* a=&l[0], *b=&r[0];
~~~~~~~~~~~~~~~~~~~~~~~~
if(r[p[x]]==x) {a=&r[0]; b=&l[0];}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a[p[x]] = b[x]; b[x] = p[x]; p[x] = p[p[x]];
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
if(p[x] != null) {
~~~~~~~~~~~~~~~~~~~
if(a[p[x]] == b[x]) a[p[x]] = x;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
else b[p[x]] = x; }
~~~~~~~~~~~~~~~~~~~~
if(a[b[x]] != null) p[a[b[x]]] = b[x];
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
update(l[b[x]]); update(r[b[x]]);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
update(p[update(b[x])] = x); } }; // from Antony at UCF.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~
void deal(){
~~~~~~~~~~~~~
ll n , m;
~~~~~~~~~~
cin>>n>>m;
~~~~~~~~~~~
ll cnt = n+1;
~~~~~~~~~~~~~~
LinkCutTree lk;
~~~~~~~~~~~~~~~~
lk.init(2*n);
~~~~~~~~~~~~~~
vector<ll > edg;
~~~~~~~~~~~~~~~~~
vector<pair<ll,ll > > all;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fori(m){
~~~~~~~~~
ll a, b;
~~~~~~~~~
cin>>a>>b;
~~~~~~~~~~~
if(lk.findroot(a) != lk.findroot(b)){
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lk.link(a, cnt);
~~~~~~~~~~~~~~~~~
lk.link(cnt,b);
~~~~~~~~~~~~~~~~
all.pb(mp(a,b));
~~~~~~~~~~~~~~~~~
edg.pb(cnt);
~~~~~~~~~~~~~
++cnt;
~~~~~~~
}
~~
else
~~~~~
lk.pathUpdate(a,b,1);
~~~~~~~~~~~~~~~~~~~~~~
}
~~
fori(edg.size()){
~~~~~~~~~~~~~~~
pipes.cpp:118:2: note: in expansion of macro 'fori'
fori(edg.size()){
^~~~