oj.uz

Submission #1089872

# Submission time Handle Problem Language Result Execution time Memory
1089872 2024-09-17T10:42:24 Z Neco_arc Jail (JOI22_jail) C++17
49 / 100
 472 ms 529676 KB 
#include <bits/stdc++.h>
#ifdef LOCAL
#include <bits/debug.hpp>
#endif // LOCAL

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Jail"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 120001

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

int n, q, N;
int deg[35 * maxn], h[maxn];
int cha[maxn][18], Sx[maxn][18], Tx[maxn][18];
int Sv[maxn], Tv[maxn], S[maxn], T[maxn];
vector<int> edges[maxn], g[35 * maxn];

void pre_dfs(int u, int par) {
    for(int v : edges[u]) if(v != par) {
        h[v] = h[u] + 1, cha[v][0] = u;
        fi(i, 1, 17) cha[v][i] = cha[cha[v][i - 1]][i - 1];

        pre_dfs(v, u);
    }
}

int lca(int u, int v) {
    if(h[u] < h[v]) swap(u, v);
    fid(i, 17, 0) if(h[u] - (1 << i) >= h[v]) u = cha[u][i];
    fid(i, 17, 0) if(cha[u][i] != cha[v][i]) u = cha[u][i], v = cha[v][i];
    return u == v ? u : cha[u][0];
}

void AddS(int id, int x, int h) {
    fid(i, 17, 0) if(getbit(h, i)) {
        g[Sx[x][i]].push_back(id);
        x = cha[x][i];
    }
}

void AddT(int id, int x, int h) {
    fid(i, 17, 0) if(getbit(h, i)) {
        g[id].push_back(Tx[x][i]);
        x = cha[x][i];
    }
}

bool TopoSort() {
    queue<int> q;
    fi(u, 1, N) for(int v : g[u]) ++deg[v];
    fi(i, 1, N) {
        if(!deg[i]) q.push(i);
    }

    int cnt = 0;
    while(!q.empty()) {
        ++cnt;
        int u = q.front(); q.pop();
        for(int v : g[u]) {
            --deg[v];
            if(!deg[v]) q.push(v);
        }
    }

    return cnt == N;

}

void reset() {
    fi(i, 1, n) fi(j, 0, 17) cha[i][j] = 0;
    fi(i, 1, n) edges[i].clear(), Sv[i] = Tv[i] = 0;
    fi(i, 1, N) g[i].clear(), deg[i] = 0;
    N = 0;
}

void solve()
{

    cin >> n;
    fi(i, 1, n - 1) {
        int x, y; cin >> x >> y;
        edges[x].push_back(y), edges[y].push_back(x);
    }

    cin >> q;
    fi(i, 1, q) {
        cin >> S[i] >> T[i];
        Sv[S[i]] = i, Tv[T[i]] = i;
    }

    N = q;
    pre_dfs(1, 0);

    fi(j, 0, 17) fi(i, 1, n) {
        Tx[i][j] = ++N;
        Sx[i][j] = ++N;
    }

    fi(j, 0, 17) fi(i, 1, n) if(cha[i][j]) {
        int p = cha[i][j], ids = Sx[i][j + 1], idt = Tx[i][j + 1];
        g[Sx[i][j]].push_back(ids);
        g[idt].push_back(Tx[i][j]);

//        cout << Sx[i][j] << " " << ids << '\n';

        if(p) {
            g[Sx[p][j]].push_back(ids);
//            cout << Sx[p][j] << " " << ids << '\n';
            g[idt].push_back(Tx[p][j]);
        }
    }


    fi(i, 1, n) {
        int p = cha[i][0];
        if(Sv[p]) g[Sv[p]].push_back(Sx[i][0]);
        if(Tv[p]) g[Tx[i][0]].push_back(Tv[p]);
    }


    fi(i, 1, q) {
        int x = S[i], y = T[i], p = lca(x, y);
        if(x == y) continue;

        int Ls = h[x] - h[p], Lt = h[y] - h[p];

        if(Ls >= 2) {
            AddS(i, x, Ls - 1);
            AddT(i, x, Ls - 1);
        }

        if(Lt >= 2) {
            AddS(i, y, Lt - 1);
            AddT(i, y, Lt - 1);
        }

        int tv[] = {x, y, p};
        for(int u : tv) {
            if(Sv[u] && Sv[u] != i) g[Sv[u]].push_back(i);
            if(Tv[u] && Tv[u] != i) g[i].push_back(Tv[u]);
        }
    }

    if(TopoSort()) cout << "Yes\n";
    else cout << "No\n";

    reset();
}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

jail.cpp: In function 'int main()':
jail.cpp:170:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:171:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 101724 KB Output is correct
2 Correct 49 ms 101716 KB Output is correct
3 Correct 45 ms 101724 KB Output is correct
4 Correct 66 ms 102224 KB Output is correct
5 Correct 91 ms 102744 KB Output is correct
6 Correct 47 ms 102224 KB Output is correct
7 Correct 46 ms 102236 KB Output is correct
8 Correct 48 ms 102236 KB Output is correct
9 Correct 134 ms 110880 KB Output is correct
10 Runtime error 472 ms 529676 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 101712 KB Output is correct
2 Correct 43 ms 101712 KB Output is correct
3 Correct 47 ms 102228 KB Output is correct
4 Correct 46 ms 102224 KB Output is correct
5 Correct 47 ms 102236 KB Output is correct
6 Correct 45 ms 101980 KB Output is correct
7 Correct 47 ms 101968 KB Output is correct
8 Correct 45 ms 101968 KB Output is correct
9 Correct 47 ms 101964 KB Output is correct
10 Correct 54 ms 102180 KB Output is correct
11 Correct 46 ms 101980 KB Output is correct
12 Correct 43 ms 102004 KB Output is correct
13 Correct 43 ms 101968 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 101712 KB Output is correct
2 Correct 43 ms 101712 KB Output is correct
3 Correct 47 ms 102228 KB Output is correct
4 Correct 46 ms 102224 KB Output is correct
5 Correct 47 ms 102236 KB Output is correct
6 Correct 45 ms 101980 KB Output is correct
7 Correct 47 ms 101968 KB Output is correct
8 Correct 45 ms 101968 KB Output is correct
9 Correct 47 ms 101964 KB Output is correct
10 Correct 54 ms 102180 KB Output is correct
11 Correct 46 ms 101980 KB Output is correct
12 Correct 43 ms 102004 KB Output is correct
13 Correct 43 ms 101968 KB Output is correct
14 Correct 44 ms 101828 KB Output is correct
15 Correct 43 ms 101716 KB Output is correct
16 Correct 46 ms 102224 KB Output is correct
17 Correct 46 ms 102376 KB Output is correct
18 Correct 49 ms 102224 KB Output is correct
19 Correct 45 ms 101724 KB Output is correct
20 Correct 46 ms 102236 KB Output is correct
21 Correct 47 ms 101972 KB Output is correct
22 Correct 46 ms 102224 KB Output is correct
23 Correct 44 ms 101712 KB Output is correct
24 Correct 46 ms 101896 KB Output is correct
25 Correct 48 ms 102040 KB Output is correct
26 Correct 43 ms 101980 KB Output is correct
27 Correct 45 ms 101972 KB Output is correct
28 Correct 44 ms 101716 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 101712 KB Output is correct
2 Correct 43 ms 101712 KB Output is correct
3 Correct 47 ms 102228 KB Output is correct
4 Correct 46 ms 102224 KB Output is correct
5 Correct 47 ms 102236 KB Output is correct
6 Correct 45 ms 101980 KB Output is correct
7 Correct 47 ms 101968 KB Output is correct
8 Correct 45 ms 101968 KB Output is correct
9 Correct 47 ms 101964 KB Output is correct
10 Correct 54 ms 102180 KB Output is correct
11 Correct 46 ms 101980 KB Output is correct
12 Correct 43 ms 102004 KB Output is correct
13 Correct 43 ms 101968 KB Output is correct
14 Correct 44 ms 101828 KB Output is correct
15 Correct 43 ms 101716 KB Output is correct
16 Correct 46 ms 102224 KB Output is correct
17 Correct 46 ms 102376 KB Output is correct
18 Correct 49 ms 102224 KB Output is correct
19 Correct 45 ms 101724 KB Output is correct
20 Correct 46 ms 102236 KB Output is correct
21 Correct 47 ms 101972 KB Output is correct
22 Correct 46 ms 102224 KB Output is correct
23 Correct 44 ms 101712 KB Output is correct
24 Correct 46 ms 101896 KB Output is correct
25 Correct 48 ms 102040 KB Output is correct
26 Correct 43 ms 101980 KB Output is correct
27 Correct 45 ms 101972 KB Output is correct
28 Correct 44 ms 101716 KB Output is correct
29 Correct 47 ms 102180 KB Output is correct
30 Correct 50 ms 102188 KB Output is correct
31 Correct 48 ms 102036 KB Output is correct
32 Correct 48 ms 102228 KB Output is correct
33 Correct 46 ms 102224 KB Output is correct
34 Correct 46 ms 101968 KB Output is correct
35 Correct 48 ms 101972 KB Output is correct
36 Correct 48 ms 101976 KB Output is correct
37 Correct 43 ms 101972 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 101712 KB Output is correct
2 Correct 43 ms 101712 KB Output is correct
3 Correct 47 ms 102228 KB Output is correct
4 Correct 46 ms 102224 KB Output is correct
5 Correct 47 ms 102236 KB Output is correct
6 Correct 45 ms 101980 KB Output is correct
7 Correct 47 ms 101968 KB Output is correct
8 Correct 45 ms 101968 KB Output is correct
9 Correct 47 ms 101964 KB Output is correct
10 Correct 54 ms 102180 KB Output is correct
11 Correct 46 ms 101980 KB Output is correct
12 Correct 43 ms 102004 KB Output is correct
13 Correct 43 ms 101968 KB Output is correct
14 Correct 44 ms 101828 KB Output is correct
15 Correct 43 ms 101716 KB Output is correct
16 Correct 46 ms 102224 KB Output is correct
17 Correct 46 ms 102376 KB Output is correct
18 Correct 49 ms 102224 KB Output is correct
19 Correct 45 ms 101724 KB Output is correct
20 Correct 46 ms 102236 KB Output is correct
21 Correct 47 ms 101972 KB Output is correct
22 Correct 46 ms 102224 KB Output is correct
23 Correct 44 ms 101712 KB Output is correct
24 Correct 46 ms 101896 KB Output is correct
25 Correct 48 ms 102040 KB Output is correct
26 Correct 43 ms 101980 KB Output is correct
27 Correct 45 ms 101972 KB Output is correct
28 Correct 44 ms 101716 KB Output is correct
29 Correct 47 ms 102180 KB Output is correct
30 Correct 50 ms 102188 KB Output is correct
31 Correct 48 ms 102036 KB Output is correct
32 Correct 48 ms 102228 KB Output is correct
33 Correct 46 ms 102224 KB Output is correct
34 Correct 46 ms 101968 KB Output is correct
35 Correct 48 ms 101972 KB Output is correct
36 Correct 48 ms 101976 KB Output is correct
37 Correct 43 ms 101972 KB Output is correct
38 Correct 134 ms 110916 KB Output is correct
39 Runtime error 462 ms 529332 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 101712 KB Output is correct
2 Correct 44 ms 101832 KB Output is correct
3 Correct 43 ms 101952 KB Output is correct
4 Correct 47 ms 101712 KB Output is correct
5 Correct 52 ms 101920 KB Output is correct
6 Correct 44 ms 102068 KB Output is correct
7 Correct 44 ms 102132 KB Output is correct
8 Correct 43 ms 101724 KB Output is correct
9 Correct 43 ms 101716 KB Output is correct
10 Correct 43 ms 101928 KB Output is correct
11 Correct 43 ms 101968 KB Output is correct
12 Correct 44 ms 101932 KB Output is correct
13 Correct 77 ms 102480 KB Output is correct
14 Correct 101 ms 102736 KB Output is correct
15 Correct 92 ms 102740 KB Output is correct
16 Runtime error 323 ms 342608 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 101724 KB Output is correct
2 Correct 49 ms 101716 KB Output is correct
3 Correct 45 ms 101724 KB Output is correct
4 Correct 66 ms 102224 KB Output is correct
5 Correct 91 ms 102744 KB Output is correct
6 Correct 47 ms 102224 KB Output is correct
7 Correct 46 ms 102236 KB Output is correct
8 Correct 48 ms 102236 KB Output is correct
9 Correct 134 ms 110880 KB Output is correct
10 Runtime error 472 ms 529676 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -