답안 #59330 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59330	2018-07-21T14:37:47 Z	Benq	Usmjeri (COCI17_usmjeri)	C++14	140 / 140	1719 ms	162560 KB

usmjeri

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

DSU<3<<20> D;
// 1<<20, 1<<20, 1<<20

vector<vi> graph;
bool existEdge[2][1<<20];

int get(int z, int x) {
    return x+((z+1)<<20);
}

void prop(int z, int ind) {
    if (ind >= (1<<19)) return;
    if (!existEdge[z][2*ind]) {
        existEdge[z][2*ind] = 1;
        D.unite(get(z,ind),get(z,2*ind));
        prop(z,2*ind);
    }
    if (!existEdge[z][2*ind+1]) {
        existEdge[z][2*ind+1] = 1;
        D.unite(get(z,ind),get(z,2*ind+1));
        prop(z,2*ind+1);
    }
}

void updSeg(int z, int x, int l, int r, int ind = 1, int lo = 0, int hi = (1<<19)-1) {
    if (r < lo || l > hi) return;
    if (l <= lo && hi <= r) {
        D.unite(x,get(z,ind));
        prop(z,ind);
        return;
    } 
    int mid = (lo+hi)/2;
    updSeg(z,x,l,r,2*ind,lo,mid);
    updSeg(z,x,l,r,2*ind+1,mid+1,hi);
}

template <int V> struct HeavyLight { // sum queries, sum updates
    int parent[V], heavy[V], depth[V];
    int root[V], treePos[V];

    void init() {
        int n = sz(graph)-1;
        FOR(i,1,n+1) heavy[i] = -1;
        parent[1] = -1, depth[1] = 0;
        dfs(1);
        for (int i = 1, currentPos = 0; i <= n; ++i)
    		if (parent[i] == -1 || heavy[parent[i]] != i)
    			for (int j = i; j != -1; j = heavy[j]) {
    				root[j] = i;
    				treePos[j] = currentPos++;
    			}
    }
    
    int dfs(int v) {
        int size = 1, maxSubtree = 0;
        for (auto u : graph[v]) if (u != parent[v]) {
            parent[u] = v;
            depth[u] = depth[v] + 1;
            int subtree = dfs(u);
            if (subtree > maxSubtree) heavy[v] = u, maxSubtree = subtree;
            size += subtree;
        }
        return size;
    }

    void processPath(int x, int u, int v) {
        for (; root[u] != root[v]; ) {
            if (depth[root[u]] > depth[root[v]]) {
                updSeg(0, x, treePos[root[u]], treePos[u]);
                u = parent[root[u]];
            } else {
                updSeg(1, x, treePos[root[v]], treePos[v]);
                v = parent[root[v]];
            }
        }
        if (depth[u] > depth[v]) {
            updSeg(0, x, treePos[v]+1,treePos[u]);
        } else {
            updSeg(1, x, treePos[u]+1, treePos[v]); // assumes values are stored in edges, not vertices
        }
    }
};

HeavyLight<1<<19> H;
int N,M;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M; graph.resize(N+1);
    F0R(i,N-1) {
        int a,b; cin >> a >> b;
        graph[a].pb(b), graph[b].pb(a);
    }
    H.init();
    F0R(i,M) {
        int x,y; cin >> x >> y;
        H.processPath(2*i,x,y);
        H.processPath(2*i+1,y,x);
    }
    set<int> s;
    FOR(i,2,N+1) {
        int a = D.get(i-1+(3<<19));
        int b = D.get(i-1+(5<<19));
        if (a == b) {
            cout << 0;
            exit(0);
        }
        s.insert(a);
        s.insert(b);
    }
    ll res = 1;
    F0R(i,sz(s)/2) res = 2*res%MOD;
    cout << res;
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	403 ms	46712 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	878 ms	96268 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	96268 KB	Output is correct
2	Correct	33 ms	96268 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	96268 KB	Output is correct
2	Correct	30 ms	96268 KB	Output is correct

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	96268 KB	Output is correct
2	Correct	35 ms	96268 KB	Output is correct

Subtask #6
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	96268 KB	Output is correct
2	Correct	36 ms	96268 KB	Output is correct

Subtask #7
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1605 ms	96268 KB	Output is correct
2	Correct	1586 ms	96512 KB	Output is correct
3	Correct	505 ms	96512 KB	Output is correct

Subtask #8
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1494 ms	111924 KB	Output is correct
2	Correct	1362 ms	119984 KB	Output is correct
3	Correct	1129 ms	119984 KB	Output is correct

Subtask #9
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1550 ms	133016 KB	Output is correct
2	Correct	1602 ms	137868 KB	Output is correct
3	Correct	981 ms	137868 KB	Output is correct

Subtask #10
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1719 ms	153904 KB	Output is correct
2	Correct	1503 ms	162560 KB	Output is correct
3	Correct	606 ms	162560 KB	Output is correct

답안 #59330

Compilation message