Submission #667246

#	Time	Username	Problem	Language	Result	Execution time	Memory
667246		Kahou	Jail (JOI22_jail)	C++14	100 / 100	1497 ms	386112 KiB

jail

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1.2e5 + 50;
const int M = 5e6 + 50, LG = 20;
int n, om, m, par[LG][N], h[N], id[LG][N][2], mark[N][2];
int s[M], t[M];
int d[M];
vector<int> adj[N];
vector<int> adj2[M];
queue<int> q;

void dfs(int u, int p) {
        h[u] = h[p]+1;
        par[0][u] = p;

        if (mark[u][0]) {
                adj2[id[0][u][0]].push_back(mark[u][0]);
                d[mark[u][0]]++;
        }
        if (mark[u][1]) {
                adj2[mark[u][1]].push_back(id[0][u][1]);
                d[id[0][u][1]]++;
        }

        for (int v:adj[u]) {
                if (v == p) continue;
                dfs(v, u);
        }
}
int Par(int u, int x) {
        for (int k = 0; k < LG; k++) {
                if (x>>k&1) u = par[k][u];
        }
        return u;
}
int LCA(int u, int v) {
        if (h[u] > h[v]) swap(u, v);
        v = Par(v, h[v]-h[u]);
        for (int k = LG-1; k >= 0; k--){ 
                if (par[k][u] != par[k][v]) {
                        u = par[k][u];
                        v = par[k][v];
                }
        }
        if (u == v) return u;
        return par[0][u];
}

void solve() {
        cin >> n;
        for (int i = 1; i <= n-1; i++) {
                int u, v;
                cin >> u >> v;
                adj[u].push_back(v);
                adj[v].push_back(u);
        }
        cin >> m;
        om = m;
        for (int i = 1; i <= m; i++) {
                cin >> s[i] >> t[i];
                mark[s[i]][0] = mark[t[i]][1] = i;
        }
        for (int k = 0; k < LG; k++) {
                for (int u = 1; u <= n; u++) {
                        id[k][u][0] = ++m;
                }
        }
        for (int k = 0; k < LG; k++) {
                for (int u = 1; u <= n; u++) {
                        id[k][u][1] = ++m;
                }
        }

        dfs(1, 0);

        for (int k = 1; k < LG; k++) {
                for (int u = 1; u <= n; u++) {
                        par[k][u] = par[k-1][par[k-1][u]];

                        adj2[id[k][u][0]].push_back(id[k-1][u][0]);
                        d[id[k-1][u][0]]++;
                        adj2[id[k][u][0]].push_back(id[k-1][par[k-1][u]][0]);
                        d[id[k-1][par[k-1][u]][0]]++;

                        adj2[id[k-1][u][1]].push_back(id[k][u][1]);
                        d[id[k][u][1]]++;
                        adj2[id[k-1][par[k-1][u]][1]].push_back(id[k][u][1]);
                        d[id[k][u][1]]++;
                }
        }


        for (int i = 1; i <= om; i++) {
                int r = LCA(s[i], t[i]);
                int u, x;
                u = par[0][s[i]];
                x = h[u]-h[r]+1;
                for (int k = 0; k < LG; k++) {
                        if (x>>k&1) {
                                adj2[i].push_back(id[k][u][0]);
                                d[id[k][u][0]]++;
                                u = par[k][u];
                        }
                }
                u = s[i];
                x = h[u]-h[r] + (r != t[i]);
                for (int k = 0; k < LG; k++) {
                        if (x>>k&1) {
                                adj2[id[k][u][1]].push_back(i);
                                d[i]++;
                                u = par[k][u];
                        }
                }
                u = t[i];
                x = h[u]-h[r] + (r != s[i]);
                for (int k = 0; k < LG; k++) {
                        if (x>>k&1) {
                                adj2[i].push_back(id[k][u][0]);
                                d[id[k][u][0]]++;
                                u = par[k][u];
                        }
                }
                u = par[0][t[i]];
                x = h[u]-h[r]+1;
                for (int k = 0; k < LG; k++) {
                        if (x>>k&1) {
                                adj2[id[k][u][1]].push_back(i);
                                d[i]++;
                                u = par[k][u];
                        }
                }
        }
        for (int u = 1; u <= m; u++) {
                if (!d[u]) q.push(u);
        }
        while (q.size()) {
                int u = q.front();
                q.pop();
                for (int v:adj2[u]) {
                        d[v]--;
                        if (!d[v]) q.push(v);
                }
        }
        bool flg = 1;
        for (int u = 1; u <= m; u++) {
                flg = flg&&(!d[u]);
        }
        cout << (flg?"Yes":"No") << endl;

        for (int u = 0; u <= n; u++) {
                h[u] = 0;
                adj[u].clear();
                mark[u][0] = mark[u][1] = 0;
                for (int k = 0; k < LG; k++) {
                        par[k][u] = 0;
                        id[k][u][0] = 0;
                        id[k][u][1] = 0;
                }
        }
        for (int u = 0; u <= m; u++) {
                adj2[u].clear();
                s[u] = t[u] = 0;
                d[u] = 0;
        }
        m = om = 0;
}

int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int tc;
        cin >> tc;
        while(tc--)
                solve();
        return 0;
}

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