oj.uz

답안 #891846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
891846 2023-12-24T08:34:35 Z vjudge1 Jail (JOI22_jail) C++17
5 / 100
 3257 ms 69984 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<type1, null_type, less_equal<type1>, rb_tree_tag, tree_order_statistics_node_update>;

using namespace std;
using namespace __gnu_pbds;

const int mod = 1e9+7;
const double PI = acos(-1.0);
const double epsilon = 1e-6;
const int N = 1.2e5+5;
vector<int> g[N];
int n;

int sz[N], d[N], h[N], up[20][N];
int top[N], chain[N], tin[N], tout[N], rt, timer, pos[N];

void clean(){
	d[1] = 0;
	for(int i = 0; i < N; i++){
		pos[i] = 0;
		g[i].clear();
		for(int j = 0; j < 20; j++) up[j][i] = 0;
	}
}

struct SegmentTree{
	int tree[N * 4];
	int lazy[N * 4];
	function<int(int,int)> f;
	int type;
	
	SegmentTree(function<int(int,int)> func, int ty){
		f = func;
		type = ty;
	}
	
	void build(const vector<int> &a,int v, int l, int r){
		if(l == r){
			tree[v] = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(a,v * 2, l, mid);
		build(a,v * 2 + 1, mid + 1, r);
		tree[v] = f(tree[v * 2], tree[v * 2 + 1]);
	}
	
	void push(int v, int tl, int tr) {
		if (lazy[v] == 0) return;
		if (tl != tr) {
			lazy[v * 2] += lazy[v];
			lazy[v * 2 + 1] += lazy[v];
		}
		tree[v] += lazy[v];
		lazy[v] = 0;
	}
	 
	void update(int l, int r, int x, int v, int tl, int tr) {
		push(v, tl, tr);
		if (l > tr || tl > r) return ;
		if (l <= tl && tr <= r) {
			lazy[v] = x;
			push(v, tl, tr);
			return;
		}
		int tm = (tl + tr) / 2;
		update(l, r, x, v * 2, tl, tm);
		update(l, r, x, v * 2 + 1, tm + 1, tr);
		tree[v] = f(tree[v * 2], tree[v * 2 + 1]);
	}
	 
	int get(int v, int tl, int tr, int l, int r) {
		push(v, tl, tr);
		if (l > tr || tl > r) return type;
		if (l <= tl && tr <= r) return tree[v];
		int tm = (tl + tr) / 2;
		return f(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
	}
	
	void clean(){
		for(int i = 0; i < N * 4; i++) tree[i] = 0,lazy[i] = 0;
	}
	
	int search(int v,int tl,int tr){
		push(v, tl, tr);
		if(tl == tr){
			return pos[tl];
		}
		int tm = (tl + tr) / 2;
		if(tree[v * 2] + lazy[v * 2] == tree[v]) return search(v*2,tl,tm);
		else return search(v*2+1,tm+1,tr);
	}
};

function<int(int,int)> minm = [](int a,int b){
	return min(a,b);
};

function<int(int,int)> summ = [](int a,int b){
	return a + b;
};

SegmentTree seg(summ,0),T(minm,1e18),quer(summ,0);

void dfs(int u, int p){
    up[0][u] = p;
    for ( int i = 1; i < 20; i++ ){
        up[i][u] = up[i - 1][up[i - 1][u]];
    }
    sz[u] = 1;
    for ( auto &v: g[u] ){
        if ( v != p ){
            d[v] = d[u] + 1;
            dfs(v, u);
            sz[u] += sz[v];
        }
    }
    for ( auto &v: g[u] ){
        if ( v != p ){
            if ( h[u] == -1 || sz[h[u]] < sz[v] ){
                h[u] = v;
            }
        }
    }
}

int lca(int u, int v){
    if ( d[u] < d[v] ) swap(u, v);
    int df = d[u] - d[v];
    for ( int i = 0; i < 20; i++ ){
        if ( df >> i & 1 ){
            u = up[i][u];
        }
    }
    if ( u == v ){
        return u;
    }
    for ( int i = 19; i >= 0; i-- ){
        if ( up[i][u] != up[i][v] ){
            u = up[i][u];
            v = up[i][v];
        }
    }
    return up[0][u];
};

void HLD(int u, int p){
    tin[u] = ++timer;
    pos[timer] = u;
    chain[u] = rt;
    if ( top[rt] == -1 ){
        top[rt] = u;
    }
    if ( h[u] != -1 ) HLD(h[u], u);
    for ( auto &v: g[u] ){
        if ( v != p && h[u] != v ){
            rt++; HLD(v, u);
        }
    }
    tout[u] = timer;
}

void upd(int u,int v,int val){
	if ( d[u] < d[v] ) swap(u, v);
    while ( chain[u] != chain[v] ){
        int nxt = top[chain[u]];
        seg.update(tin[nxt],tin[u],val,1,1,n);
        T.update(tin[nxt],tin[u],val,1,1,n);
        u = up[0][nxt];
    }
    seg.update(tin[v],tin[u],val,1,1,n);
    T.update(tin[v],tin[u],val,1,1,n);
}

void update(int u,int v, int val){
	int lc = lca(u,v);
	upd(u,lc,val); upd(v,lc,val);
    seg.update(tin[lc],tin[lc],-val,1,1,n);
    T.update(tin[lc],tin[lc],-val,1,1,n);
}

int qry(int u,int v){
	if ( d[u] < d[v] ) swap(u, v);
	int res = 0;
    while ( chain[u] != chain[v] ){
        int nxt = top[chain[u]];
        res += quer.get(1,1,n,tin[nxt],tin[u]);
        u = up[0][nxt];
    }
    res += quer.get(1,1,n,tin[v],tin[u]);
    return res;
}

int query(int u,int v){
	int lc = lca(u,v);
	return qry(u,lc) + qry(v,lc);
}

void solve(){
	cin >> n;
	for(int i = 1; i < n; i++){
		int u,v; cin >> u >> v;
		g[u].pb(v); g[v].pb(u);
	}
    int m; cin >> m;
    vector<pair<int,int> > qr(m);
    for(auto &[l,r] : qr) cin >> l >> r;
    quer.clean();
    seg.clean();
    T.clean();
    for(int i = 0; i < N; i++) top[i] = -1, h[i] = -1;
    rt = 0; timer = 0;
    dfs(1,1); HLD(1,1);
    
    vector<int> vec(n+1);
    for(int i = 0; i < m; i++) vec[qr[i].ss] = i;
    vector<int> A(n+1,1e18);
    for(auto [u,v] : qr) A[v] = 0;
    T.build(A,1,1,n);
    
    for(auto [u,v] : qr) quer.update(tin[u],tin[u],1,1,1,n);
    
    for(auto [u,v] : qr) update(u,v,1);
    
    //for(int i = 1; i <= n; i++) cout << seg.get(1,1,n,tin[i],tin[i]) << " \n"[i == n];
    //for(int i = 1; i <= n; i++) cout << T.get(1,1,n,tin[i],tin[i]) << " \n"[i == n];
    //for(int i = 1; i <= n; i++) cout << quer.get(1,1,n,tin[i],tin[i]) << " \n"[i == n];
    
    for(int time = 0; time < m; time++){
		if(T.tree[1] != 1){
			cout << "No\n";
			clean();
			return;
		}
		
		int i = vec[T.search(1,1,n)];
		auto [u,v] = qr[i];
		update(u,v,-1);
		quer.update(tin[u],tin[u],-1,1,1,n);
		if(!(query(u,v) == 0 && seg.get(1,1,n,tin[v],tin[v]) == 0)){
			cout << "No\n";
			clean();
			return;
		}
		T.update(tin[v],tin[v],1e18,1,1,n);
	}
	cout << "Yes\n";
    clean();
}

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

Compilation message

jail.cpp:261:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  261 | main(){
      | ^~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 52060 KB Output is correct
2 Correct 13 ms 52060 KB Output is correct
3 Correct 8 ms 52060 KB Output is correct
4 Correct 1451 ms 52472 KB Output is correct
5 Correct 3257 ms 52868 KB Output is correct
6 Correct 68 ms 52164 KB Output is correct
7 Correct 70 ms 52160 KB Output is correct
8 Correct 75 ms 52056 KB Output is correct
9 Correct 116 ms 53984 KB Output is correct
10 Correct 45 ms 66640 KB Output is correct
11 Correct 3198 ms 52724 KB Output is correct
12 Correct 3232 ms 53144 KB Output is correct
13 Correct 265 ms 67928 KB Output is correct
14 Correct 140 ms 67924 KB Output is correct
15 Correct 229 ms 67924 KB Output is correct
16 Correct 476 ms 69968 KB Output is correct
17 Correct 331 ms 68344 KB Output is correct
18 Correct 491 ms 69984 KB Output is correct
19 Correct 331 ms 68564 KB Output is correct
20 Correct 213 ms 68320 KB Output is correct
21 Correct 172 ms 68180 KB Output is correct
22 Correct 137 ms 68288 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 52056 KB Output is correct
2 Correct 7 ms 52060 KB Output is correct
3 Correct 68 ms 52168 KB Output is correct
4 Incorrect 69 ms 52056 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 52056 KB Output is correct
2 Correct 7 ms 52060 KB Output is correct
3 Correct 68 ms 52168 KB Output is correct
4 Incorrect 69 ms 52056 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 52056 KB Output is correct
2 Correct 7 ms 52060 KB Output is correct
3 Correct 68 ms 52168 KB Output is correct
4 Incorrect 69 ms 52056 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 52056 KB Output is correct
2 Correct 7 ms 52060 KB Output is correct
3 Correct 68 ms 52168 KB Output is correct
4 Incorrect 69 ms 52056 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 52060 KB Output is correct
2 Correct 12 ms 52060 KB Output is correct
3 Correct 14 ms 52060 KB Output is correct
4 Correct 8 ms 52060 KB Output is correct
5 Correct 3124 ms 52564 KB Output is correct
6 Incorrect 69 ms 52056 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 52060 KB Output is correct
2 Correct 13 ms 52060 KB Output is correct
3 Correct 8 ms 52060 KB Output is correct
4 Correct 1451 ms 52472 KB Output is correct
5 Correct 3257 ms 52868 KB Output is correct
6 Correct 68 ms 52164 KB Output is correct
7 Correct 70 ms 52160 KB Output is correct
8 Correct 75 ms 52056 KB Output is correct
9 Correct 116 ms 53984 KB Output is correct
10 Correct 45 ms 66640 KB Output is correct
11 Correct 3198 ms 52724 KB Output is correct
12 Correct 3232 ms 53144 KB Output is correct
13 Correct 265 ms 67928 KB Output is correct
14 Correct 140 ms 67924 KB Output is correct
15 Correct 229 ms 67924 KB Output is correct
16 Correct 476 ms 69968 KB Output is correct
17 Correct 331 ms 68344 KB Output is correct
18 Correct 491 ms 69984 KB Output is correct
19 Correct 331 ms 68564 KB Output is correct
20 Correct 213 ms 68320 KB Output is correct
21 Correct 172 ms 68180 KB Output is correct
22 Correct 137 ms 68288 KB Output is correct
23 Correct 8 ms 52056 KB Output is correct
24 Correct 7 ms 52060 KB Output is correct
25 Correct 68 ms 52168 KB Output is correct
26 Incorrect 69 ms 52056 KB Output isn't correct
27 Halted 0 ms 0 KB -