oj.uz

Submission #882511

# Submission time Handle Problem Language Result Execution time Memory
882511 2023-12-03T09:44:54 Z LucaIlie Jail (JOI22_jail) C++17
0 / 100
 3890 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;

struct prisoner {
    int b, w;
};

const int MAX_N = 1.2e5;
const int MAX_M = MAX_N;
int parent[MAX_N + 1], depth[MAX_N + 1], bedroom[MAX_N + 1], workroom[MAX_N + 1], in[MAX_N + 1];
vector <int> edges[MAX_N + 1], g[MAX_M + 1];
prisoner prisoners[MAX_M + 1];

void dfs( int u, int p ) {
    depth[u] = depth[p] + 1;
    parent[u] = p;
    for ( int v: edges[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
    }
}

int main() {
    int t;

    cin >> t;
    while ( t-- ) {
        int n, m;

        cin >> n;
        for ( int v = 1; v <= n; v++ ) {
            edges[v].clear();
            workroom[v] = 0;
            bedroom[v] = 0;
        }
        for ( int i = 0; i < n - 1; i++ ) {
            int u, v;
            cin >> u >> v;
            edges[u].push_back( v );
            edges[v].push_back( u );
        }
        cin >> m;
        for ( int i = 1; i <= m; i++ ) {
            g[i].clear();
            in[i] = 0;
        }
        for ( int i = 1; i <= m; i++ )
            cin >> prisoners[i].b >> prisoners[i].w;

        dfs( 1, 0 );

        for ( int i = 1; i <= m; i++ ) {
            bedroom[prisoners[i].b] = i;
            workroom[prisoners[i].w] = i;
        }
        for ( int i = 1; i <= m; i++ ) {
            int u = prisoners[i].b, v = prisoners[i].w;

            if ( depth[u] < depth[v] )
                swap( u, v );

            while ( depth[u] > depth[v] ) {
                if ( bedroom[u] != 0 && bedroom[u] != i )
                    g[bedroom[u]].push_back( i );
                if ( workroom[u] != 0 && workroom[u] != i )
                    g[i].push_back( workroom[u] );
                u = parent[u];
            }

            while ( u != v ) {
                if ( bedroom[u] != 0 && bedroom[u] != i )
                    g[bedroom[u]].push_back( i );
                if ( workroom[u] != 0 && workroom[u] != i )
                    g[i].push_back( workroom[u] );
                if ( bedroom[v] != 0 && bedroom[v] != i )
                    g[bedroom[v]].push_back( i );
                if ( workroom[v] != 0 && workroom[u] != i )
                    g[i].push_back( workroom[v] );
                u = parent[u];
                v = parent[v];
            }
            if ( bedroom[u] != 0 && bedroom[u] != i )
                g[bedroom[u]].push_back( i );
            if ( workroom[u] != 0 && workroom[u] != i )
                g[i].push_back( workroom[u] );
        }
        for ( int i = 1; i <= m; i++ ) {
            sort( g[i].begin(), g[i].end() );
            g[i].resize( unique( g[i].begin(), g[i].end() ) - g[i].begin() );
            for ( int j: g[i] )
                in[j]++;
        }

        queue <int> q;
        for ( int i = 1; i <= m; i++ ) {
            if ( in[i] == 0 )
                q.push( i );
        }
        int pasi = 0;
        while ( !q.empty() ) {
            int u = q.front();
            q.pop();
            pasi++;

            for ( int v: g[u] ) {
                in[v]--;
                if ( in[v] == 0 )
                    q.push( v );
            }
        }

        cout << (pasi == m ? "Yes\n" : "No\n");
    }

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 18 ms 8796 KB Output is correct
5 Correct 35 ms 9308 KB Output is correct
6 Correct 3 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 5 ms 8732 KB Output is correct
9 Correct 123 ms 12116 KB Output is correct
10 Correct 197 ms 21160 KB Output is correct
11 Correct 11 ms 8792 KB Output is correct
12 Correct 75 ms 9660 KB Output is correct
13 Correct 199 ms 50620 KB Output is correct
14 Correct 269 ms 64200 KB Output is correct
15 Runtime error 3890 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Incorrect 1 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 18 ms 8796 KB Output is correct
5 Correct 35 ms 9308 KB Output is correct
6 Correct 3 ms 8540 KB Output is correct
7 Correct 3 ms 8540 KB Output is correct
8 Correct 5 ms 8732 KB Output is correct
9 Correct 123 ms 12116 KB Output is correct
10 Correct 197 ms 21160 KB Output is correct
11 Correct 11 ms 8792 KB Output is correct
12 Correct 75 ms 9660 KB Output is correct
13 Correct 199 ms 50620 KB Output is correct
14 Correct 269 ms 64200 KB Output is correct
15 Runtime error 3890 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -