QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#642222#8551. DFS Order 5youthpaulWA 30ms3612kbC++203.8kb2024-10-15 11:58:522024-10-15 11:58:52

Judging History

你现在查看的是最新测评结果

  • [2024-10-15 11:58:52]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:3612kb
  • [2024-10-15 11:58:52]
  • 提交

answer

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;

    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n + 5, T{});
    }

    void update(int p, const T &v) { //在位置 p 加 v
        while(p <= n){
            a[p] += v;
            p += p & -p;
        }
    }
    
    T query(int p) {
        T ans{};
        while(p > 0){
            ans += a[p];
            p -= p & -p;
        }
        return ans;
    }

    T rangeSum(int l, int r) {
        return query(r) - query(l - 1); //前缀和
    }

    int find_first(T sum){ //找到第一个 query(p) >= sum 的位置 p
        int p = 0;
        T val = 0;
        for(int i = std::__lg(n); i >= 0; --i)
            if((p | 1 << i) <= n && val + a[p | 1 << i] < sum){
                p |= 1 << i;
                val += a[p];
            }
        return p + 1;
    }

    int find_last(T sum){ //找到最后一个 query(p) <= sum 的位置 p
        int p = 0;
        T val = 0;
        for(int i = std::__lg(n); i >= 0; --i)
            if((p | 1 << i) <= n && val + a[p | 1 << i] <= sum){
                p |= 1 << i;
                val += a[p];
            }
        return p;
    }
};

const int N = 100005;
const int K = 17;

std::vector<int> g[N];
int f[N][K + 1];
int h[N];
int dfn[N];
int up[N];
int tot;
int sz[N];

void dfs0(int u, int fa){
	h[u] = h[fa] + 1;
	f[u][0] = fa;
	dfn[u] = ++tot;
	sz[u] = 1;
	for(int k = 1; (1 << k) <= h[u]; ++k)
		f[u][k] = f[f[u][k - 1]][k - 1];
	for(auto v : g[u])
		if(v != fa){
			dfs0(v, u);
			sz[u] += sz[v];
		}
	up[u] = tot;
}

int lca(int u, int v){
	if(h[u] < h[v]) std::swap(u, v);
	for(int k = K; k >= 0; --k)
		if(h[u] - (1 << k) >= h[v])
			u = f[u][k];
	if(u == v) return u;
	for(int k = K; k >= 0; --k)
		if(f[u][k] != f[v][k]){
			u = f[u][k];
			v = f[v][k];
		}
	return f[u][0];
}


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n, q;
    std::cin >> n >> q;
    fore(i, 1, n){
    	int u, v;
    	std::cin >> u >> v;
    	g[u].push_back(v);
    	g[v].push_back(u);
    }
    
    dfs0(1, 0);
    
    Fenwick<int> fen(n);
    
    int Q = q;
    int C = 0;
    while(q--){
        ++C;
    	int m;
    	std::cin >> m;
    	std::vector<int> a(m);
    	fore(i, 0, m) std::cin >> a[i];
    	std::vector<int> p;

        if(C == 899){
            std::cout << m << ' ';
            for(auto x : a) std::cout << x << ' ';
        }
    	
    	auto check = [&]() -> bool {
    		if(m == 1) return true;
    		p.push_back(dfn[a[0]]);
    		fen.update(dfn[a[0]], 1);
    		if(a[0] != 1){
    			p.push_back(1);
    			fen.update(1, 1);
    		}
    		
    		fore(i, 1, m){
    			int u = a[i - 1], w = a[i];
    			if(fen.rangeSum(dfn[w], up[w])) return false;
    			if(f[w][0] == u){
    				fen.update(dfn[w], 1);
    				p.push_back(dfn[w]);
    				continue;
    			}
    			if(fen.rangeSum(dfn[u], up[u]) != sz[u]) return false;
    			if(lca(u, f[w][0]) == f[w][0] && lca(u, w) != w){
    				fen.update(dfn[w], 1);
    				p.push_back(dfn[w]);
    				continue;
    			}
    			return false;
   		 	}
   		 	
   		 	return true;
    	};
    	
        bool tag = check();
    	if(Q < 100) std::cout << (tag ? "Yes" : "No") << endl;
    	for(auto x : p)	fen.update(x, -1);
    }
    
    return 0;
}














Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3612kb

input:

6 7
1 2
1 3
2 4
3 5
2 6
2 4 1
2 4 2
2 4 3
2 4 4
2 4 5
2 4 6
6 1 2 6 4 3 5

output:

No
No
Yes
No
No
Yes
Yes

result:

ok 7 tokens

Test #2:

score: -100
Wrong Answer
time: 30ms
memory: 3572kb

input:

10 100000
7 2
1 7
7 10
8 6
8 7
1 3
4 5
9 5
5 8
8 8 9 7 2 8 1 6 1
4 8 3 5 2
6 7 10 3 9 9 1
1 1
8 10 3 2 9 3 8 7 3
7 5 6 2 8 5 9 1
6 3 4 6 2 1 3
5 8 9 2 4 9
1 3
2 1 5
5 8 5 1 7 9
10 5 2 9 2 6 4 10 6 3 8
3 4 5 8
2 8 4
9 4 10 1 2 4 3 3 6 3
1 3
6 1 1 6 8 3 1
3 7 3 2
3 9 1 5
4 3 7 8 10
9 4 2 3 10 2 5 4 3 ...

output:

3 5 4 10 

result:

wrong answer 1st words differ - expected: 'No', found: '3'