oj.uz

Submission #600681

# Submission time Handle Problem Language Result Execution time Memory
600681 2022-07-21T06:58:03 Z Mazaalai Werewolf (IOI18_werewolf) C++17
0 / 100
 131 ms 19676 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) {
    bool vis[n], vis1[n]; 
    memset(vis, 0, sizeof(vis));
    memset(vis1, 0, sizeof(vis1));
    vis[st] = 1;
    queue <int> bfs; bfs.push(st);
    while(!bfs.empty()) {
        int x = bfs.front(); bfs.pop();
        for (auto el : paths[x]) {
            if (vis[el] || el < l) continue;
            vis[el] = 1;
            bfs.push(l);
        }
    }

    vis1[ed] = 1;
    bfs.push(ed);
    while(!bfs.empty()) {
        int x = bfs.front(); bfs.pop();
        if (vis[x]) return 1;
        for (auto el : paths[x]) {
            if (vis1[el] || el > r) continue;
            vis1[el] = 1;
            bfs.push(l);
        }
    }
    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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -