Submission #113036

#	Time	Username	Problem	Language	Result	Execution time	Memory
113036		MAMBA	Pipes (CEOI15_pipes)	C++17	50 / 100	3525 ms	23688 KiB

pipes

    #pragma GCC optimize("Ofast")
    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
    #include <bits/stdc++.h> 
     
    using namespace std;
     
    #define rep(i , j , k) for (int i = j; i < (int)k; i++)
    #define pb push_back
    #define mt make_tuple
    #define all(x) x.begin(),x.end()
     
    typedef long long ll;
    typedef pair<int , int> pii;
    typedef pair<ll, ll> pll;
    typedef long double ld;
    typedef complex<ld> point;
    typedef pair<ld , ld> pld;
    typedef vector<int> vi;
     
    inline void fileIO(string s) {
    //	freopen((s + ".in").c_str(), "r", stdin);
    	freopen((s + ".out").c_str(), "w", stdout);
    }
     
    template<class T , class S>
    inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
    template<class T , class S>
    inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }
     
    constexpr int N = 1e5 + 10;
     
    constexpr int MOD = 1e6 + 7;
     
    template<typename T>
    inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
    template<typename S, typename T>
    inline S add(S &l, T r) { return mod(l += r); }
     
    int n, m;
    vi adj[N];
     
    int p[N];
     
    int get_par(int v) {
    	if (p[v]) 
    		return p[v] = get_par(p[v]);
    	return v;
    }
     
    inline bool merge(int v, int u) {
    	v = get_par(v);
    	u = get_par(u);
     
    	if (v == u) return false;
    	p[v] = u;
    	return true;
    }
     
    bitset<N> mark;
     
    int RMQ[18][N << 1], Tm , nu[N] , st[N], en[N], rev[N], junk[N << 1], ptr;
    void dfs(int v, int pa = 0) {
      	rev[Tm] = v;
      	junk[ptr++] = Tm;
      	nu[v] = Tm++;
      st[v] = ptr - 1;
    	mark[v] = true;
    	for (auto e : adj[v])
    		if (e ^ pa) {
    			dfs(e , v);
            	junk[ptr++] = nu[v];
            }
    	en[v] = ptr;
    }
     
	int shit[N << 1];
	int rmq(int l , int r) {
      int len = r - l;
      return min(RMQ[shit[len]][l] , RMQ[shit[len]][r - (1 << shit[len])]);
    }

    inline int LCA(int v, int u) {
 		if (st[v] > st[u]) swap(v , u);
      if (en[v] >= en[u]) return v;
      return rev[rmq(en[v] , st[u])];
    }
     
    int val[N];
    void dfs2(int v , int pa = 0) {
    	mark[v] = true;
    	for (auto e : adj[v])
    		if (e ^ pa) {
    			dfs2(e , v);
    			val[v] += val[e];
    		}
    	if (val[v] == 1)
    		cout << v << ' ' << pa << '\n'; 
    }
     
    int main() {
    	ios::sync_with_stdio(0);
    	cin.tie(0); cout.tie(0);
     	
      int local = 0;
      rep(i , 1 , N << 1) {
        shit[i] = local;
		if (i == (1 << (local + 1)))
          local++;
      }
      
    #ifndef LOCAL
    	//fileIO("superposition");
    #endif
     
     
    	
    	cin >> n >> m;
     
    	rep(i , 0 , m) 
    	{
    		int u , v;
    		cin >> u >> v;
    		if (merge(u , v)) {
    			adj[u].pb(v);
    			adj[v].pb(u);
    		}
    	}
     
      	st[0] = -1;
      
    	rep(i , 1 , n + 1)
    		if (!mark[i])
    			dfs(i);
    	en[0] = Tm;
      	
      	rep(i , 0 , ptr)
          RMQ[0][i] = junk[i];
      	rep(i , 1 , 18)
          rep(j , 0 , ptr) {
          	RMQ[i][j] = RMQ[i - 1][j];
          if (j + (1 << (i - 1)) < ptr)
            smin(RMQ[i][j] , RMQ[i - 1][j + (1 << (i - 1))]);
        }
      
    	cin.seekg(0);
     
    	cin >> n >> m;
    	rep(i , 0 , m) {
    		int u , v;
    		cin >> u >> v;
    		int lca = LCA(u , v);
    		if (lca == u || lca == v) {
    			val[u ^ v ^ lca]++;
    			val[lca]--;
    		}
    		else {
    			val[u]++;
    			val[v]++;
    			val[lca] -= 2;
    		}
    	}
     
    	mark.reset();
     
    	rep(i , 1 , n + 1)
    		if (!mark[i])
    			dfs2(i);
    			
    	return 0;
     
    }

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