제출 #142660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
142660		nots0fast	Pipes (CEOI15_pipes)	C++17	40 / 100	5096 ms	15868 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision(12)<<fixed
#define ss second
#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()){
		ll a= edg[i];
		if(lk.pathAggregate(a,a) == 0)
			cout<<all[i].ff<<" "<<all[i].ss<<endl;
	}
}
 
 
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();
}

컴파일 시 표준 에러 (stderr) 메시지

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()){
  ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10