oj.uz

Submission #1000217

# Submission time Handle Problem Language Result Execution time Memory
1000217 2024-06-17T06:26:08 Z onbert Jail (JOI22_jail) C++17
0 / 100
 5000 ms 27168 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 120005, maxN = 480005, lgn = 17, INF = 1e18;
int n, m;
vector<int> ADJ[maxn], adj[maxn];
pair<int,int> a[maxn];
int sz[maxn], fa[maxn], d[maxn], newid[maxn], lim[maxn], cnter = 0;

void dfs1(int u) {
    sz[u] = 1;
    int f = -1;
    for (int &v:ADJ[u]) {
        if (sz[v]) {
            f = v;
            continue;
        }
        dfs1(v);
        sz[u] += sz[v];
    }
    if (f!=-1) ADJ[u].erase(find(ADJ[u].begin(), ADJ[u].end(), f));
    for (int j=1;j<ADJ[u].size();j++) if (sz[ADJ[u][j]] > sz[ADJ[u][0]]) swap(ADJ[u][0], adj[u][j]);
}
void dfs2(int u) {
    cnter++;
    newid[u] = cnter;
    for (int v:ADJ[u]) {
        d[cnter+1] = d[newid[u]] + 1;
        dfs2(v);
        fa[newid[v]] = newid[u];
    }
    lim[u] = cnter;
}

void solve() {
    cin >> n;
    for (int i=1;i<=n;i++) sz[i] = 0, adj[i].clear(), ADJ[i].clear();
    cnter = 0;
    for (int i=1;i<=n-1;i++) {
        int u, v;
        cin >> u >> v;
        ADJ[u].push_back(v);
        ADJ[v].push_back(u);
    }
    fa[1] = 0, d[1] = 0;
    dfs1(1); dfs2(1);
    bool guy[n+1];
    for (int i=1;i<=n;i++) guy[i] = 0;
    for (int i=1;i<=n;i++) a[i] = {-1, -1};
    cin >> m;
    for (int i=1;i<=m;i++) {
        int s, t;
        cin >> s >> t;
        s = newid[s], t = newid[t];
        a[t] = {s, t};
        guy[s] = true;
    }
    bool yes[n+1], no[n+1];
    for (int cnt = 0; cnt < m; cnt++) {
        for (int i=1;i<=n;i++) yes[i] = (a[i].first!=-1), no[i] = 0;
        for (int i=1;i<=n;i++) {
            if (a[i].first==-1) continue;
            auto [u, v] = a[i];
            auto [s, t] = a[i];
            yes[i] = !guy[t];
            no[s] = true;
            // cout << i << " " << a[i].first << " " << a[i].second << endl;
            while (u!=v) {
                if (d[u] > d[v]) swap(u, v);
                v = fa[v];
                // cout << u << " " << v << endl;
                if (v != t) no[v] = true;
                if (v != s) yes[i] &= (!guy[v]);
            }
        }
        bool ok = false;
        for (int i=1;i<=n;i++) if (yes[i] && !no[i]) {
            // cout << a[i].first << " " << a[i].second << endl;
            guy[i] = true;
            guy[a[i].first] = false;
            a[i] = {-1, -1};
            ok = true;
            break;
        }
        if (!ok) {cout << "No\n"; return;}
    }
    cout << "Yes\n";
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

Compilation message

jail.cpp: In function 'void dfs1(long long int)':
jail.cpp:22:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int j=1;j<ADJ[u].size();j++) if (sz[ADJ[u][j]] > sz[ADJ[u][0]]) swap(ADJ[u][0], adj[u][j]);
      |                  ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 8 ms 6232 KB Output is correct
5 Correct 14 ms 6748 KB Output is correct
6 Correct 5 ms 5980 KB Output is correct
7 Correct 4 ms 5980 KB Output is correct
8 Correct 7 ms 6220 KB Output is correct
9 Correct 2045 ms 8096 KB Output is correct
10 Execution timed out 5087 ms 27168 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5976 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 3 ms 6208 KB Output is correct
4 Runtime error 10 ms 11992 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5976 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 3 ms 6208 KB Output is correct
4 Runtime error 10 ms 11992 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5976 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 3 ms 6208 KB Output is correct
4 Runtime error 10 ms 11992 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5976 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 3 ms 6208 KB Output is correct
4 Runtime error 10 ms 11992 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB Output is correct
2 Correct 3 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 5 ms 6236 KB Output is correct
6 Correct 3 ms 5980 KB Output is correct
7 Correct 3 ms 5980 KB Output is correct
8 Runtime error 8 ms 11952 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 8 ms 6232 KB Output is correct
5 Correct 14 ms 6748 KB Output is correct
6 Correct 5 ms 5980 KB Output is correct
7 Correct 4 ms 5980 KB Output is correct
8 Correct 7 ms 6220 KB Output is correct
9 Correct 2045 ms 8096 KB Output is correct
10 Execution timed out 5087 ms 27168 KB Time limit exceeded
11 Halted 0 ms 0 KB -