oj.uz

Submission #600704

# Submission time Handle Problem Language Result Execution time Memory
600704 2022-07-21T07:16:50 Z Mazaalai Werewolf (IOI18_werewolf) C++17
15 / 100
 196 ms 19680 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;
using VI = vector <int>;
const int N = 3e3+1;
int n, m, q;
vector <int> paths[N];
int ans[N];
struct Query {
    int st, ed, l, r, id;
    // l means I can use city x in human form (l <= x < n)
    // r means I can use city x in wolf form (0 <= x <= r)
};
int solve(int st, int ed, int l, int r) {
    // cout << st << ' ' << ed << ' ' << l << ' ' << r << '\n';
    int vis[n];
    memset(vis, 0, sizeof(vis));
    queue <int> bfs; bfs.push(st);
    queue <int> bfs1; bfs1.push(ed);
    while(!bfs.empty()) {
        int x = bfs.front(); bfs.pop();
        if (x < l || vis[x]==1) continue;
        vis[x] = 1;
        for (auto el : paths[x]) 
            bfs.push(el);
    }
    while(!bfs1.empty()) {
        int x = bfs1.front(); bfs1.pop();
        if (x > r || vis[x]==2) continue;
        if (vis[x] == 1) return 1;
        vis[x] = 2;
        for (auto el : paths[x]) 
            bfs1.push(el);
    }
    return 0;
}
VI check_validity(int _N, VI X, VI Y, VI ST, VI ED, VI L, VI R) {
    n = _N;
    m = sz(X);
    q = sz(ST);
    for (int i = 0; i < m; i++) {
        paths[X[i]].pb(Y[i]);
        paths[Y[i]].pb(X[i]);
    }
    vector <Query> queries;
    for (int i = 0; i < q; i++) 
        queries.pb({ST[i], ED[i], L[i], R[i], i});
    
    VI res(q);
    for (int i = 0; i < q; i++) {
        // res[i] = ans[i];
        res[i] = solve(queries[i].st, queries[i].ed, queries[i].l, queries[i].r);
    }
    return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 149 ms 752 KB Output is correct
11 Correct 98 ms 724 KB Output is correct
12 Correct 9 ms 724 KB Output is correct
13 Correct 129 ms 748 KB Output is correct
14 Correct 90 ms 724 KB Output is correct
15 Correct 196 ms 824 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 167 ms 19680 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 149 ms 752 KB Output is correct
11 Correct 98 ms 724 KB Output is correct
12 Correct 9 ms 724 KB Output is correct
13 Correct 129 ms 748 KB Output is correct
14 Correct 90 ms 724 KB Output is correct
15 Correct 196 ms 824 KB Output is correct
16 Runtime error 167 ms 19680 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -