oj.uz

Submission #1089873

# Submission time Handle Problem Language Result Execution time Memory
1089873 2024-09-17T10:43:11 Z Neco_arc Jail (JOI22_jail) C++17
49 / 100
 575 ms 580608 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) 120005

using namespace std;

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

int n, q, N;
int deg[36 * maxn], h[maxn];
int cha[maxn][19], Sx[maxn][19], Tx[maxn][19];
int Sv[maxn], Tv[maxn], S[maxn], T[maxn];
vector<int> edges[maxn], g[36 * 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 104532 KB Output is correct
2 Correct 44 ms 104528 KB Output is correct
3 Correct 44 ms 104676 KB Output is correct
4 Correct 89 ms 105044 KB Output is correct
5 Correct 106 ms 105300 KB Output is correct
6 Correct 54 ms 105040 KB Output is correct
7 Correct 47 ms 105040 KB Output is correct
8 Correct 48 ms 105040 KB Output is correct
9 Correct 134 ms 113364 KB Output is correct
10 Runtime error 575 ms 580608 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 48 ms 104720 KB Output is correct
2 Correct 43 ms 104540 KB Output is correct
3 Correct 49 ms 105040 KB Output is correct
4 Correct 45 ms 105052 KB Output is correct
5 Correct 46 ms 104788 KB Output is correct
6 Correct 56 ms 105044 KB Output is correct
7 Correct 46 ms 105040 KB Output is correct
8 Correct 47 ms 105032 KB Output is correct
9 Correct 47 ms 104784 KB Output is correct
10 Correct 47 ms 105048 KB Output is correct
11 Correct 45 ms 104884 KB Output is correct
12 Correct 54 ms 104796 KB Output is correct
13 Correct 46 ms 104788 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 104720 KB Output is correct
2 Correct 43 ms 104540 KB Output is correct
3 Correct 49 ms 105040 KB Output is correct
4 Correct 45 ms 105052 KB Output is correct
5 Correct 46 ms 104788 KB Output is correct
6 Correct 56 ms 105044 KB Output is correct
7 Correct 46 ms 105040 KB Output is correct
8 Correct 47 ms 105032 KB Output is correct
9 Correct 47 ms 104784 KB Output is correct
10 Correct 47 ms 105048 KB Output is correct
11 Correct 45 ms 104884 KB Output is correct
12 Correct 54 ms 104796 KB Output is correct
13 Correct 46 ms 104788 KB Output is correct
14 Correct 43 ms 104532 KB Output is correct
15 Correct 43 ms 104792 KB Output is correct
16 Correct 51 ms 105060 KB Output is correct
17 Correct 45 ms 104784 KB Output is correct
18 Correct 50 ms 104912 KB Output is correct
19 Correct 45 ms 104528 KB Output is correct
20 Correct 49 ms 105040 KB Output is correct
21 Correct 47 ms 105040 KB Output is correct
22 Correct 47 ms 105028 KB Output is correct
23 Correct 45 ms 104532 KB Output is correct
24 Correct 47 ms 104788 KB Output is correct
25 Correct 51 ms 104784 KB Output is correct
26 Correct 47 ms 104784 KB Output is correct
27 Correct 51 ms 105048 KB Output is correct
28 Correct 47 ms 104532 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 104720 KB Output is correct
2 Correct 43 ms 104540 KB Output is correct
3 Correct 49 ms 105040 KB Output is correct
4 Correct 45 ms 105052 KB Output is correct
5 Correct 46 ms 104788 KB Output is correct
6 Correct 56 ms 105044 KB Output is correct
7 Correct 46 ms 105040 KB Output is correct
8 Correct 47 ms 105032 KB Output is correct
9 Correct 47 ms 104784 KB Output is correct
10 Correct 47 ms 105048 KB Output is correct
11 Correct 45 ms 104884 KB Output is correct
12 Correct 54 ms 104796 KB Output is correct
13 Correct 46 ms 104788 KB Output is correct
14 Correct 43 ms 104532 KB Output is correct
15 Correct 43 ms 104792 KB Output is correct
16 Correct 51 ms 105060 KB Output is correct
17 Correct 45 ms 104784 KB Output is correct
18 Correct 50 ms 104912 KB Output is correct
19 Correct 45 ms 104528 KB Output is correct
20 Correct 49 ms 105040 KB Output is correct
21 Correct 47 ms 105040 KB Output is correct
22 Correct 47 ms 105028 KB Output is correct
23 Correct 45 ms 104532 KB Output is correct
24 Correct 47 ms 104788 KB Output is correct
25 Correct 51 ms 104784 KB Output is correct
26 Correct 47 ms 104784 KB Output is correct
27 Correct 51 ms 105048 KB Output is correct
28 Correct 47 ms 104532 KB Output is correct
29 Correct 49 ms 104788 KB Output is correct
30 Correct 49 ms 104980 KB Output is correct
31 Correct 50 ms 105040 KB Output is correct
32 Correct 50 ms 104792 KB Output is correct
33 Correct 54 ms 105040 KB Output is correct
34 Correct 47 ms 104792 KB Output is correct
35 Correct 48 ms 104904 KB Output is correct
36 Correct 49 ms 104788 KB Output is correct
37 Correct 46 ms 104784 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 104720 KB Output is correct
2 Correct 43 ms 104540 KB Output is correct
3 Correct 49 ms 105040 KB Output is correct
4 Correct 45 ms 105052 KB Output is correct
5 Correct 46 ms 104788 KB Output is correct
6 Correct 56 ms 105044 KB Output is correct
7 Correct 46 ms 105040 KB Output is correct
8 Correct 47 ms 105032 KB Output is correct
9 Correct 47 ms 104784 KB Output is correct
10 Correct 47 ms 105048 KB Output is correct
11 Correct 45 ms 104884 KB Output is correct
12 Correct 54 ms 104796 KB Output is correct
13 Correct 46 ms 104788 KB Output is correct
14 Correct 43 ms 104532 KB Output is correct
15 Correct 43 ms 104792 KB Output is correct
16 Correct 51 ms 105060 KB Output is correct
17 Correct 45 ms 104784 KB Output is correct
18 Correct 50 ms 104912 KB Output is correct
19 Correct 45 ms 104528 KB Output is correct
20 Correct 49 ms 105040 KB Output is correct
21 Correct 47 ms 105040 KB Output is correct
22 Correct 47 ms 105028 KB Output is correct
23 Correct 45 ms 104532 KB Output is correct
24 Correct 47 ms 104788 KB Output is correct
25 Correct 51 ms 104784 KB Output is correct
26 Correct 47 ms 104784 KB Output is correct
27 Correct 51 ms 105048 KB Output is correct
28 Correct 47 ms 104532 KB Output is correct
29 Correct 49 ms 104788 KB Output is correct
30 Correct 49 ms 104980 KB Output is correct
31 Correct 50 ms 105040 KB Output is correct
32 Correct 50 ms 104792 KB Output is correct
33 Correct 54 ms 105040 KB Output is correct
34 Correct 47 ms 104792 KB Output is correct
35 Correct 48 ms 104904 KB Output is correct
36 Correct 49 ms 104788 KB Output is correct
37 Correct 46 ms 104784 KB Output is correct
38 Correct 141 ms 112552 KB Output is correct
39 Runtime error 572 ms 579296 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 45 ms 104620 KB Output is correct
2 Correct 43 ms 104528 KB Output is correct
3 Correct 44 ms 104528 KB Output is correct
4 Correct 45 ms 104532 KB Output is correct
5 Correct 56 ms 104784 KB Output is correct
6 Correct 44 ms 104888 KB Output is correct
7 Correct 47 ms 104788 KB Output is correct
8 Correct 43 ms 104528 KB Output is correct
9 Correct 44 ms 104528 KB Output is correct
10 Correct 43 ms 104784 KB Output is correct
11 Correct 54 ms 104664 KB Output is correct
12 Correct 46 ms 104796 KB Output is correct
13 Correct 80 ms 104788 KB Output is correct
14 Correct 107 ms 104788 KB Output is correct
15 Correct 87 ms 104792 KB Output is correct
16 Runtime error 333 ms 377788 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 104532 KB Output is correct
2 Correct 44 ms 104528 KB Output is correct
3 Correct 44 ms 104676 KB Output is correct
4 Correct 89 ms 105044 KB Output is correct
5 Correct 106 ms 105300 KB Output is correct
6 Correct 54 ms 105040 KB Output is correct
7 Correct 47 ms 105040 KB Output is correct
8 Correct 48 ms 105040 KB Output is correct
9 Correct 134 ms 113364 KB Output is correct
10 Runtime error 575 ms 580608 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -