Submission #593013

#	Time	Username	Problem	Language	Result	Execution time	Memory
593013		jhnah917	Jail (JOI22_jail)	C++14	21 / 100	5081 ms	3472 KiB

jail

#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();
}

Compilation message (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;
      |                  ^

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23