제출 #593013

#제출 시각아이디문제언어결과실행 시간메모리
593013jhnah917Jail (JOI22_jail)C++14
21 / 100
5081 ms3472 KiB
#include <bits/stdc++.h>
using namespace std;

int N, K, P[22][121212], D[121212], C[121212];
vector<int> G[121212];

void DFS(int v, int b=-1){
    for(auto i : G[v]) if(i != b) P[0][i] = v, D[i] = D[v] + 1, DFS(i, v);
}

int LCA(int u, int v){
    if(D[u] < D[v]) swap(u, v);
    int diff = D[u] - D[v];
    for(int i=0; diff; i++, diff>>=1) if(diff & 1) u = P[i][u];
    if(u == v) return u;
    for(int i=21; i>=0; i--) if(P[i][u] != P[i][v]) u = P[i][u], v = P[i][v];
    return P[0][u];
}

void Clear(){
    for(int i=1; i<=N; i++) G[i].clear();
}

bool Check(int u, int v){
    int l = LCA(u, v), res = !C[l];
    while(u != l) res &= !C[u], u = P[0][u];
    while(v != l) res &= !C[v], v = P[0][v];
    return res;
}

void Solve(){
    cin >> N; Clear();
    for(int i=1,s,e; i<N; i++) cin >> s >> e, G[s].push_back(e), G[e].push_back(s);
    DFS(1);
    for(int i=1; i<22; i++) for(int j=1; j<=N; j++) P[i][j] = P[i-1][P[i-1][j]];

    cin >> K;
    vector<pair<int,int>> V(K);
    for(auto &[a,b] : V) cin >> a >> b;
    sort(V.begin(), V.end());
    do{
        bool flag = true;
        for(auto [a,b] : V) C[a] = 1;
        for(auto [a,b] : V){
            C[a] = 0;
            flag &= Check(a, b);
            C[b] = 1;
        }
        for(auto [a,b] : V) C[b] = 0;
        if(flag){ cout << "Yes\n"; return; }
    }while(next_permutation(V.begin(), V.end()));
    cout << "No\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int TC; cin >> TC;
    for(int tc=1; tc<=TC; tc++) Solve();
}

컴파일 시 표준 에러 (stderr) 메시지

jail.cpp: In function 'void Solve()':
jail.cpp:39:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for(auto &[a,b] : V) cin >> a >> b;
      |               ^
jail.cpp:43:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |         for(auto [a,b] : V) C[a] = 1;
      |                  ^
jail.cpp:44:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |         for(auto [a,b] : V){
      |                  ^
jail.cpp:49:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |         for(auto [a,b] : V) C[b] = 0;
      |                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...