oj.uz

Submission #776281

# Submission time Handle Problem Language Result Execution time Memory
776281 2023-07-07T14:28:30 Z eltu0815 Jail (JOI22_jail) C++14
72 / 100
 5000 ms 1046392 KB 
#include <bits/stdc++.h>
#define MAX 500005
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
 
using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
int n, m, tt;
int parent[120005][25];
int s[120005], t[120005], dep[120005], deg[120005];
int S[120005], T[120005];
vector<int> graph[120005];
vector<int> DAG[120005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> tt;
    while(tt--) {
        cin >> n;
        for(int i = 1; i <= n; ++i) graph[i].clear(), DAG[i].clear();
        for(int i = 1; i <= n; ++i) deg[i] = S[i] = T[i] = 0;
        for(int i = 1; i <= n; ++i) for(int j = 0; j <= 20; ++j) parent[i][j] = 0;
        for(int i = 1; i <= n - 1; ++i) {
            int a, b; cin >> a >> b;
            graph[a].push_back(b);
            graph[b].push_back(a);
        }
        
        cin >> m;
        for(int i = 1; i <= m; ++i) cin >> s[i] >> t[i];
        
        auto dfs = [&](auto&& self, int node, int par) -> void {
            parent[node][0] = par; dep[node] = dep[par] + 1;
            for(auto v : graph[node]) if(v != par) self(self, v, node);
        };
        dfs(dfs, 1, 0);
        for(int j = 1; j < 20; ++j) for(int i = 1; i <= n; ++i) parent[i][j] = parent[parent[i][j - 1]][j - 1];
        
        auto LCA = [&](int u, int v) -> int {
            if(dep[u] < dep[v]) swap(u, v);
            int diff = dep[u] - dep[v], j = 0;
            while(diff) {
                if(diff & 1) u = parent[u][j];
                diff >>= 1; ++j;
            }
            if(u == v) return u;
            for(int i = 19; i >= 0; --i) {
                if(parent[u][i] != parent[v][i]) {
                    u = parent[u][i];
                    v = parent[v][i];
                }
            }
            return parent[u][0];
        };
        
        for(int i = 1; i <= m; ++i) S[s[i]] = T[t[i]] = i;
        for(int i = 1; i <= m; ++i) {
            int p = LCA(s[i], t[i]);
            for(int tmp : {s[i], t[i]}) {
                while(tmp != p) {
                    if(S[tmp] && i != S[tmp]) DAG[S[tmp]].push_back(i), deg[i]++;
                    if(T[tmp] && i != T[tmp]) DAG[i].push_back(T[tmp]), deg[T[tmp]]++;
                    tmp = parent[tmp][0];
                }
            }
            if(S[p] && i != S[p]) DAG[S[p]].push_back(i), deg[i]++;
            if(T[p] && i != T[p]) DAG[i].push_back(T[p]), deg[T[p]]++;
        }
        
        queue<int> q; int cnt = 0;
        for(int i = 1; i <= m; ++i) if(deg[i] == 0) q.push(i);
        while(!q.empty()) {
            int node = q.front(); q.pop(); ++cnt;
            for(auto v : DAG[node]) if(--deg[v] == 0) q.push(v);
        }
        
        if(cnt == m) cout << "Yes\n";
        else cout << "No\n";
    }
    
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5928 KB Output is correct
2 Correct 3 ms 5960 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Correct 10 ms 6228 KB Output is correct
5 Correct 18 ms 6252 KB Output is correct
6 Correct 5 ms 5996 KB Output is correct
7 Correct 4 ms 6076 KB Output is correct
8 Correct 5 ms 6100 KB Output is correct
9 Correct 79 ms 9072 KB Output is correct
10 Correct 341 ms 28560 KB Output is correct
11 Correct 7 ms 6100 KB Output is correct
12 Correct 28 ms 6212 KB Output is correct
13 Correct 128 ms 57388 KB Output is correct
14 Correct 124 ms 71088 KB Output is correct
15 Execution timed out 5123 ms 1046392 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 4 ms 5972 KB Output is correct
4 Correct 4 ms 5976 KB Output is correct
5 Correct 4 ms 5972 KB Output is correct
6 Correct 4 ms 5972 KB Output is correct
7 Correct 3 ms 6068 KB Output is correct
8 Correct 5 ms 5976 KB Output is correct
9 Correct 4 ms 5976 KB Output is correct
10 Correct 4 ms 5972 KB Output is correct
11 Correct 4 ms 5972 KB Output is correct
12 Correct 3 ms 5976 KB Output is correct
13 Correct 3 ms 5972 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 4 ms 5972 KB Output is correct
4 Correct 4 ms 5976 KB Output is correct
5 Correct 4 ms 5972 KB Output is correct
6 Correct 4 ms 5972 KB Output is correct
7 Correct 3 ms 6068 KB Output is correct
8 Correct 5 ms 5976 KB Output is correct
9 Correct 4 ms 5976 KB Output is correct
10 Correct 4 ms 5972 KB Output is correct
11 Correct 4 ms 5972 KB Output is correct
12 Correct 3 ms 5976 KB Output is correct
13 Correct 3 ms 5972 KB Output is correct
14 Correct 3 ms 5964 KB Output is correct
15 Correct 3 ms 5972 KB Output is correct
16 Correct 4 ms 6072 KB Output is correct
17 Correct 4 ms 5972 KB Output is correct
18 Correct 5 ms 5972 KB Output is correct
19 Correct 3 ms 5964 KB Output is correct
20 Correct 4 ms 5972 KB Output is correct
21 Correct 4 ms 5972 KB Output is correct
22 Correct 4 ms 5980 KB Output is correct
23 Correct 3 ms 5972 KB Output is correct
24 Correct 3 ms 5892 KB Output is correct
25 Correct 7 ms 5976 KB Output is correct
26 Correct 3 ms 5972 KB Output is correct
27 Correct 5 ms 6100 KB Output is correct
28 Correct 3 ms 5968 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 4 ms 5972 KB Output is correct
4 Correct 4 ms 5976 KB Output is correct
5 Correct 4 ms 5972 KB Output is correct
6 Correct 4 ms 5972 KB Output is correct
7 Correct 3 ms 6068 KB Output is correct
8 Correct 5 ms 5976 KB Output is correct
9 Correct 4 ms 5976 KB Output is correct
10 Correct 4 ms 5972 KB Output is correct
11 Correct 4 ms 5972 KB Output is correct
12 Correct 3 ms 5976 KB Output is correct
13 Correct 3 ms 5972 KB Output is correct
14 Correct 3 ms 5964 KB Output is correct
15 Correct 3 ms 5972 KB Output is correct
16 Correct 4 ms 6072 KB Output is correct
17 Correct 4 ms 5972 KB Output is correct
18 Correct 5 ms 5972 KB Output is correct
19 Correct 3 ms 5964 KB Output is correct
20 Correct 4 ms 5972 KB Output is correct
21 Correct 4 ms 5972 KB Output is correct
22 Correct 4 ms 5980 KB Output is correct
23 Correct 3 ms 5972 KB Output is correct
24 Correct 3 ms 5892 KB Output is correct
25 Correct 7 ms 5976 KB Output is correct
26 Correct 3 ms 5972 KB Output is correct
27 Correct 5 ms 6100 KB Output is correct
28 Correct 3 ms 5968 KB Output is correct
29 Correct 5 ms 6100 KB Output is correct
30 Correct 4 ms 5972 KB Output is correct
31 Correct 4 ms 6104 KB Output is correct
32 Correct 4 ms 6016 KB Output is correct
33 Correct 4 ms 5980 KB Output is correct
34 Correct 4 ms 5976 KB Output is correct
35 Correct 4 ms 6100 KB Output is correct
36 Correct 4 ms 5972 KB Output is correct
37 Correct 4 ms 6004 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 4 ms 5972 KB Output is correct
4 Correct 4 ms 5976 KB Output is correct
5 Correct 4 ms 5972 KB Output is correct
6 Correct 4 ms 5972 KB Output is correct
7 Correct 3 ms 6068 KB Output is correct
8 Correct 5 ms 5976 KB Output is correct
9 Correct 4 ms 5976 KB Output is correct
10 Correct 4 ms 5972 KB Output is correct
11 Correct 4 ms 5972 KB Output is correct
12 Correct 3 ms 5976 KB Output is correct
13 Correct 3 ms 5972 KB Output is correct
14 Correct 3 ms 5964 KB Output is correct
15 Correct 3 ms 5972 KB Output is correct
16 Correct 4 ms 6072 KB Output is correct
17 Correct 4 ms 5972 KB Output is correct
18 Correct 5 ms 5972 KB Output is correct
19 Correct 3 ms 5964 KB Output is correct
20 Correct 4 ms 5972 KB Output is correct
21 Correct 4 ms 5972 KB Output is correct
22 Correct 4 ms 5980 KB Output is correct
23 Correct 3 ms 5972 KB Output is correct
24 Correct 3 ms 5892 KB Output is correct
25 Correct 7 ms 5976 KB Output is correct
26 Correct 3 ms 5972 KB Output is correct
27 Correct 5 ms 6100 KB Output is correct
28 Correct 3 ms 5968 KB Output is correct
29 Correct 5 ms 6100 KB Output is correct
30 Correct 4 ms 5972 KB Output is correct
31 Correct 4 ms 6104 KB Output is correct
32 Correct 4 ms 6016 KB Output is correct
33 Correct 4 ms 5980 KB Output is correct
34 Correct 4 ms 5976 KB Output is correct
35 Correct 4 ms 6100 KB Output is correct
36 Correct 4 ms 5972 KB Output is correct
37 Correct 4 ms 6004 KB Output is correct
38 Correct 73 ms 9104 KB Output is correct
39 Correct 429 ms 28580 KB Output is correct
40 Correct 53 ms 8140 KB Output is correct
41 Correct 28 ms 7064 KB Output is correct
42 Correct 38 ms 8304 KB Output is correct
43 Correct 23 ms 7068 KB Output is correct
44 Correct 8 ms 6320 KB Output is correct
45 Correct 51 ms 23492 KB Output is correct
46 Correct 59 ms 23536 KB Output is correct
47 Correct 148 ms 25224 KB Output is correct
48 Correct 151 ms 25292 KB Output is correct
49 Correct 61 ms 23500 KB Output is correct
50 Correct 57 ms 23540 KB Output is correct
51 Correct 50 ms 24108 KB Output is correct
52 Correct 45 ms 24068 KB Output is correct
53 Correct 10 ms 7252 KB Output is correct
54 Correct 61 ms 23384 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5960 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Correct 3 ms 5964 KB Output is correct
5 Correct 6 ms 6104 KB Output is correct
6 Correct 3 ms 5976 KB Output is correct
7 Correct 3 ms 5968 KB Output is correct
8 Correct 3 ms 5960 KB Output is correct
9 Correct 3 ms 5964 KB Output is correct
10 Correct 3 ms 5960 KB Output is correct
11 Correct 5 ms 5972 KB Output is correct
12 Correct 4 ms 5972 KB Output is correct
13 Correct 17 ms 6208 KB Output is correct
14 Correct 24 ms 6048 KB Output is correct
15 Correct 20 ms 6152 KB Output is correct
16 Correct 59 ms 23960 KB Output is correct
17 Correct 110 ms 29404 KB Output is correct
18 Correct 237 ms 48724 KB Output is correct
19 Correct 58 ms 24012 KB Output is correct
20 Correct 63 ms 24044 KB Output is correct
21 Correct 60 ms 24012 KB Output is correct
22 Correct 91 ms 29896 KB Output is correct
23 Correct 89 ms 30388 KB Output is correct
24 Correct 87 ms 30036 KB Output is correct
25 Correct 89 ms 30076 KB Output is correct
26 Correct 89 ms 30068 KB Output is correct
27 Correct 120 ms 28612 KB Output is correct
28 Correct 114 ms 28580 KB Output is correct
29 Correct 103 ms 28612 KB Output is correct
30 Correct 76 ms 25964 KB Output is correct
31 Correct 71 ms 25928 KB Output is correct
32 Correct 84 ms 25960 KB Output is correct
33 Correct 81 ms 25948 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5928 KB Output is correct
2 Correct 3 ms 5960 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Correct 10 ms 6228 KB Output is correct
5 Correct 18 ms 6252 KB Output is correct
6 Correct 5 ms 5996 KB Output is correct
7 Correct 4 ms 6076 KB Output is correct
8 Correct 5 ms 6100 KB Output is correct
9 Correct 79 ms 9072 KB Output is correct
10 Correct 341 ms 28560 KB Output is correct
11 Correct 7 ms 6100 KB Output is correct
12 Correct 28 ms 6212 KB Output is correct
13 Correct 128 ms 57388 KB Output is correct
14 Correct 124 ms 71088 KB Output is correct
15 Execution timed out 5123 ms 1046392 KB Time limit exceeded
16 Halted 0 ms 0 KB -