제출 #600704

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600704		Mazaalai	늑대인간 (IOI18_werewolf)	C++17	15 / 100	196 ms	19680 KiB

werewolf

#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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51