QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#672685#8548. China Convex Polygon Contestlibantian#RE 0ms0kbC++233.6kb2024-10-24 18:07:502024-10-24 18:07:50

Judging History

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

  • [2024-10-24 18:07:50]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-24 18:07:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define fi first
#define se second
#define all(_a) _a.begin(), _a.end()
struct HLD {
    int n, idx;
    vector<vector<int>> ver;
    vector<int> siz, dep,cnt;
    vector<int> top, son, parent;

    HLD(int n) {
        this->n = n;
        ver.resize(n + 1);
        siz.resize(n + 1);
        dep.resize(n + 1);
        cnt.resize(n + 1);

        top.resize(n + 1);
        son.resize(n + 1);
        parent.resize(n + 1);
    }
    void add(int x, int y) { // 建立双向边
        ver[x].push_back(y);
        ver[y].push_back(x);
    }
    void dfs1(int x) {
        siz[x] = 1;
        dep[x] = dep[parent[x]] + 1;
        for (auto y : ver[x]) {
            if (y == parent[x]) continue;
            cnt[x]++;
            parent[y] = x;
            dfs1(y);
            siz[x] += siz[y];
            if (siz[y] > siz[son[x]]) {
                son[x] = y;
            }
        }
    }
    void dfs2(int x, int up) {
        top[x] = up;
        if (son[x]) dfs2(son[x], up);
        for (auto y : ver[x]) {
            if (y == parent[x] || y == son[x]) continue;
            dfs2(y, y);
        }
    }
    int lca(int x, int y) {
        while (top[x] != top[y]) {
            if (dep[top[x]] > dep[top[y]]) {
                x = parent[top[x]];
            } else {
                y = parent[top[y]];
            }
        }
        return dep[x] < dep[y] ? x : y;
    }
    int clac(int x, int y) { // 查询两点间距离
        return dep[x] + dep[y] - 2 * dep[lca(x, y)];
    }
    void work(int root = 1) { // 在此初始化
        dfs1(root);
        dfs2(root, root);
    }
};
void solve(){
    int n,q;
    cin>>n>>q;
    HLD hld(n);
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        hld.add(x,y);
    }
    hld.work();
    while(q--){
        int k;
        cin>>k;
        vector<int>a(k+1);
        set<int> s;
        for(int i=1;i<=k;i++){
            cin>>a[i];
            s.insert(a[i]);
        }
        if(s.size()!=k){
            cout<<"No"<<endl;
            continue;
        }
        // for(int i=1;i<=k;i++)cout<<a[i]<<" ";
        // cout<<endl;
        if(k==1){
            cout<<"Yes"<<endl;
            continue;
        }
        int p=a[1];
        for(int i=2;i<=k;i++)p=hld.lca(p,a[i]);
        map<int,int>mp;
        //cout<<p<<endl;
        if(p==a[1]){
            mp[hld.dep[p]]=hld.cnt[p];
            
        }else{
            
            if(hld.cnt[p]-1)mp[hld.dep[p]]=hld.cnt[p]-1;
            if(hld.cnt[a[1]])mp[hld.dep[a[1]]]=hld.cnt[a[1]];
        }
        //for(auto v:mp)cout<<v.fi<<" "<<v.se<<endl;
        //  for(int i=1;i<=k;i++)cout<<a[i]<<" ";
        // cout<<endl;
        bool is=true;
        for(int i=2;i<=k;i++){
            // cout<<i<<" "<<a[k]<<endl;
            int d=hld.dep[hld.parent[a[i]]];
            //cout<<d<<endl;
            if(mp.empty()||d!=(*mp.rbegin()).fi){
                //cout<<i<<endl;
                is=false;
                break;
            }else{
                mp[d]--;
                if(mp[d]==0)mp.erase(d);
            }
            if(hld.cnt[a[i]])mp[hld.dep[a[i]]]+=hld.cnt[a[i]];
        }
        if(is)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }

}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << setiosflags(ios::fixed) << setprecision(15);
    int T;
    T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}

详细

Test #1:

score: 0
Runtime Error

input:

3
3 10
1 5 9
1 2 3
3 10
1 5 9
1 1 4
3 10
1 5 9
1 5 10

output:


result: