oj.uz

Submission #600702

# Submission time Handle Problem Language Result Execution time Memory
600702 2022-07-21T07:15:08 Z Mazaalai Werewolf (IOI18_werewolf) C++17
15 / 100
 310 ms 19684 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;
    while(!bfs.empty()) {
        int x = bfs.front(); bfs.pop();
        if (x < l || vis[x]==1) continue;
        vis[x] = 1; bfs1.push(x);
        for (auto el : paths[x]) 
            bfs.push(el);
    }
    while(!bfs1.empty()) {
        int x = bfs1.front(); bfs1.pop();
        if (x > r || vis[x]==2) continue;
        vis[x] = 2;
        for (auto el : paths[x]) 
            bfs1.push(el);
    }
    return vis[ed]==2;
}
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 380 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 376 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 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 380 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 376 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 310 ms 860 KB Output is correct
11 Correct 212 ms 852 KB Output is correct
12 Correct 12 ms 864 KB Output is correct
13 Correct 259 ms 856 KB Output is correct
14 Correct 170 ms 852 KB Output is correct
15 Correct 215 ms 964 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 124 ms 19684 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 380 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 376 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 310 ms 860 KB Output is correct
11 Correct 212 ms 852 KB Output is correct
12 Correct 12 ms 864 KB Output is correct
13 Correct 259 ms 856 KB Output is correct
14 Correct 170 ms 852 KB Output is correct
15 Correct 215 ms 964 KB Output is correct
16 Runtime error 124 ms 19684 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -