oj.uz

Submission #1000407

# Submission time Handle Problem Language Result Execution time Memory
1000407 2024-06-17T12:44:00 Z onbert Jail (JOI22_jail) C++17
5 / 100
 9 ms 18468 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));
    // cout << u << endl;
    // for (int v:ADJ[u]) cout << v << " "; cout << endl;
    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[newid[u]] = cnter;
}

int S[maxn], T[maxn],  vis[maxn], cur = 0;
bool die = false;
vector<int> dep[maxn];

void dfs3(int u) {
    vis[u] = cur;
    for (int v:dep[u]) {
        if (!vis[v]) dfs3(v);
        else if (v==cur) die = true;
    }
}

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);
    for (int i=1;i<=n;i++) S[i] = -1, T[i] = -1;
    cin >> m;
    for (int i=1;i<=m;i++) {
        int s, t;
        cin >> s >> t;
        s = newid[s], t = newid[t];
        a[i] = {s, t};
        S[s] = i;
        T[t] = i;
    }
    for (int i=1;i<=m;i++) dep[i].clear();
    for (int i=1;i<=m;i++) {
        int u = a[i].first, v = a[i].second;
        vector<int> path;
        while (u != v) {
            if (d[u] > d[v]) swap(u, v);
            path.push_back(v);
            v = fa[v];
        }
        path.push_back(u);
        for (int j:path) {
            if (S[j]!=-1) dep[i].push_back(S[j]);
            if (T[j]!=-1) dep[T[j]].push_back(i);
        }
    }
    for (int i=1;i<=m;i++) {
        sort(dep[i].begin(), dep[i].end());
        dep[i].erase(unique(dep[i].begin(), dep[i].end()), dep[i].end());
        dep[i].erase(find(dep[i].begin(), dep[i].end(), i));
        // for (int j:dep[i]) cout << j << " "; cout << endl;
    }
    for (int i=1;i<=m;i++) vis[i] = 0;
    die = false;
    for (int i=1;i<=m;i++) if (!vis[i]) {
        cur = i;
        dfs3(i);
    }
    if (die) cout << "No\n";
    else 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:24: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]
   24 |     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 3 ms 18268 KB Output is correct
2 Correct 4 ms 18268 KB Output is correct
3 Correct 3 ms 18268 KB Output is correct
4 Incorrect 9 ms 18436 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18268 KB Output is correct
2 Correct 3 ms 18268 KB Output is correct
3 Correct 4 ms 18268 KB Output is correct
4 Correct 3 ms 18268 KB Output is correct
5 Correct 3 ms 18312 KB Output is correct
6 Correct 3 ms 18268 KB Output is correct
7 Correct 4 ms 18268 KB Output is correct
8 Correct 4 ms 18268 KB Output is correct
9 Correct 4 ms 18304 KB Output is correct
10 Correct 3 ms 18268 KB Output is correct
11 Correct 3 ms 18352 KB Output is correct
12 Correct 3 ms 18268 KB Output is correct
13 Correct 3 ms 18308 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18268 KB Output is correct
2 Correct 3 ms 18268 KB Output is correct
3 Correct 4 ms 18268 KB Output is correct
4 Correct 3 ms 18268 KB Output is correct
5 Correct 3 ms 18312 KB Output is correct
6 Correct 3 ms 18268 KB Output is correct
7 Correct 4 ms 18268 KB Output is correct
8 Correct 4 ms 18268 KB Output is correct
9 Correct 4 ms 18304 KB Output is correct
10 Correct 3 ms 18268 KB Output is correct
11 Correct 3 ms 18352 KB Output is correct
12 Correct 3 ms 18268 KB Output is correct
13 Correct 3 ms 18308 KB Output is correct
14 Correct 3 ms 18268 KB Output is correct
15 Correct 3 ms 18124 KB Output is correct
16 Incorrect 4 ms 18376 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18268 KB Output is correct
2 Correct 3 ms 18268 KB Output is correct
3 Correct 4 ms 18268 KB Output is correct
4 Correct 3 ms 18268 KB Output is correct
5 Correct 3 ms 18312 KB Output is correct
6 Correct 3 ms 18268 KB Output is correct
7 Correct 4 ms 18268 KB Output is correct
8 Correct 4 ms 18268 KB Output is correct
9 Correct 4 ms 18304 KB Output is correct
10 Correct 3 ms 18268 KB Output is correct
11 Correct 3 ms 18352 KB Output is correct
12 Correct 3 ms 18268 KB Output is correct
13 Correct 3 ms 18308 KB Output is correct
14 Correct 3 ms 18268 KB Output is correct
15 Correct 3 ms 18124 KB Output is correct
16 Incorrect 4 ms 18376 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18268 KB Output is correct
2 Correct 3 ms 18268 KB Output is correct
3 Correct 4 ms 18268 KB Output is correct
4 Correct 3 ms 18268 KB Output is correct
5 Correct 3 ms 18312 KB Output is correct
6 Correct 3 ms 18268 KB Output is correct
7 Correct 4 ms 18268 KB Output is correct
8 Correct 4 ms 18268 KB Output is correct
9 Correct 4 ms 18304 KB Output is correct
10 Correct 3 ms 18268 KB Output is correct
11 Correct 3 ms 18352 KB Output is correct
12 Correct 3 ms 18268 KB Output is correct
13 Correct 3 ms 18308 KB Output is correct
14 Correct 3 ms 18268 KB Output is correct
15 Correct 3 ms 18124 KB Output is correct
16 Incorrect 4 ms 18376 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18264 KB Output is correct
2 Correct 3 ms 18268 KB Output is correct
3 Correct 3 ms 18312 KB Output is correct
4 Correct 3 ms 18268 KB Output is correct
5 Incorrect 8 ms 18468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18268 KB Output is correct
2 Correct 4 ms 18268 KB Output is correct
3 Correct 3 ms 18268 KB Output is correct
4 Incorrect 9 ms 18436 KB Output isn't correct
5 Halted 0 ms 0 KB -