oj.uz

Submission #257403

# Submission time Handle Problem Language Result Execution time Memory
257403 2020-08-04T08:40:18 Z jtnydv25 Usmjeri (COCI17_usmjeri) C++17
140 / 140
 585 ms 86116 KB 
#include<bits/stdc++.h>
using namespace std;

const int logN = 20;

struct tree{
    int n, timer;
    vector<vector<int>> adj;
    vector<vector<int>> par;
    vector<int> depth, st, en;
    void add_edge(int a, int b){
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    tree(int n) : n(n), adj(n), par(logN, vector<int>(n)), depth(n), st(n), en(n), timer(0){}
    void input(){
        for(int i = 1; i < n; i++){
            int x, y;
            scanf("%d %d", &x, &y);
			x--; y--;
            add_edge(x, y);
        }
    }
    void rootify(int r){
        function<void(int, int, int)> dfs = [&](int s, int d, int p){
            st[s] = ++timer;
            depth[s] = d;
            par[0][s] = p;
            for(int v : adj[s])
                if(v != p)
                    dfs(v, d + 1, s);
            en[s] = timer;
        };

        dfs(r, 1, r);
        for(int j = 1;j<logN;j++)
            for(int i = 0; i < n;i++)
                par[j][i] = par[j-1][par[j-1][i]];
    }

    int lca(int a, int b){
        if(depth[a] < depth[b]) swap(a,b);
        int l = depth[a] - depth[b];
        for(int i = 0; i < logN; i++) if(l >> i & 1)
            a = par[i][a];    
        if(a == b) return a;
        for(int i = logN - 1; i >= 0; i--)
            if(par[i][a] != par[i][b])
                a = par[i][a], b = par[i][b];
        return par[0][a];
    }

    int getKth(int x, int k){
        for(int i = 0; i < logN; i++) if(k >> i & 1) x = par[i][x];
        return x;
    }
};
struct dsu{
    int n, comps, ok;
    vector<int> par;
    dsu(int n) : n(n), par(n), comps(n - 1), ok(1){
        for(int i = 0; i < n; i++) par[i] = 2 * i;
    }
    int root(int x){
		int h = par[x];
		int p = h >> 1;
		if(p == x) return h;
		return par[x] = root(p) ^ (h & 1);
    }
    bool merge(int x, int y, int e){
		int X = root(x), Y = root(y);
        x = X >> 1; y = Y >> 1;
		int parity_x = X & 1, parity_y = Y & 1;
        if(x == y){
			if(parity_x ^ parity_y ^ e) ok = 0;
			return 0;
		}
        par[x] = 2 * y + (parity_x ^ parity_y ^ e);
		comps--;
        return 1;
    }
};


int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    tree T(n);
    T.input();
	T.rootify(0);
	dsu D(n);
	dsu D2(n);
	function<void(int, int)> attach = [&](int u, int l){
		while(T.depth[u] >= T.depth[l] + 2){
			D.merge(u, T.par[0][u], 0);
			D2.merge(u, T.par[0][u], 0);
			u = D.root(u) >> 1;
		}
	};
    for(int i = 0; i < m; i++){
        int u, v;
        scanf("%d %d", &u, &v);
		u--; v--;
		if(T.depth[u] < T.depth[v]) swap(u, v);
		int l = T.lca(u, v);
		attach(u, l);
		attach(v, l);
		if(v != l){
			D2.merge(u, v, 1);
		}
    }
	int ans = D2.ok;
	for(int i = 0; i < D2.comps; i++) ans = (ans * 2) % 1000000007;
	printf("%d\n", ans);
}

Compilation message

usmjeri.cpp: In constructor 'tree::tree(int)':
usmjeri.cpp:10:28: warning: 'tree::en' will be initialized after [-Wreorder]
     vector<int> depth, st, en;
                            ^~
usmjeri.cpp:7:12: warning:   'int tree::timer' [-Wreorder]
     int n, timer;
            ^~~~~
usmjeri.cpp:15:5: warning:   when initialized here [-Wreorder]
     tree(int n) : n(n), adj(n), par(logN, vector<int>(n)), depth(n), st(n), en(n), timer(0){}
     ^~~~
usmjeri.cpp: In constructor 'dsu::dsu(int)':
usmjeri.cpp:60:17: warning: 'dsu::par' will be initialized after [-Wreorder]
     vector<int> par;
                 ^~~
usmjeri.cpp:59:12: warning:   'int dsu::comps' [-Wreorder]
     int n, comps, ok;
            ^~~~~
usmjeri.cpp:61:5: warning:   when initialized here [-Wreorder]
     dsu(int n) : n(n), par(n), comps(n - 1), ok(1){
     ^~~
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
usmjeri.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~
usmjeri.cpp: In member function 'void tree::input()':
usmjeri.cpp:19:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 29940 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 86116 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 640 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 3 ms 640 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1152 KB Output is correct
2 Correct 3 ms 1152 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 54728 KB Output is correct
2 Correct 439 ms 54756 KB Output is correct
3 Correct 244 ms 35048 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 54756 KB Output is correct
2 Correct 558 ms 54628 KB Output is correct
3 Correct 340 ms 36456 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 55412 KB Output is correct
2 Correct 374 ms 54884 KB Output is correct
3 Correct 353 ms 36584 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 55524 KB Output is correct
2 Correct 452 ms 55524 KB Output is correct
3 Correct 261 ms 34868 KB Output is correct