oj.uz

Submission #243393

# Submission time Handle Problem Language Result Execution time Memory
243393 2020-07-01T02:04:44 Z ant101 Werewolf (IOI18_werewolf) C++14
15 / 100
 316 ms 19960 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
#include "werewolf.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
#define mp make_pair
#define f first
#define s second

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 6e3+5;
const ll INF = 1e18;
const ld PI = 4*atan((ld)1);
const int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
ll vis[MX];
ll vis2[MX];
ll cl, cr;
vector<ll> adj[MX];

void dfs1(ll u) {
    trav(v, adj[u]) {
        if (!vis[v] && v>=cl) {
            vis[v] = true;
            dfs1(v);
        }
    }
}

void dfs2(ll u) {
    trav(v, adj[u]) {
        if (!vis2[v] && v<=cr) {
            vis2[v] = true;
            dfs2(v);
        }
    }
}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    int Q = S.size();
    F0R (i, sz(X)) {
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }
    std::vector<int> A(Q);
    for (int i = 0; i < Q; ++i) {
        memset(vis, 0, sizeof(vis));
        memset(vis2, 0, sizeof(vis2));
        cl = L[i];
        cr = R[i];
        if (S[i]>=L[i]) {
            vis[S[i]] = true;
            dfs1(S[i]);
        }
        if (E[i]<=R[i]) {
            vis2[E[i]] = true;
            dfs2(E[i]);
        }
        bool cango = false;
        F0R (j, N) {
            if (vis[j] && vis2[j] && j >= cl && j <= cr) {
                cango = true;
                break;
            }
        }
        if (vis[E[i]]) {
            cango = true;
        }
        A[i] = cango;
    }
    return A;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 285 ms 1016 KB Output is correct
11 Correct 163 ms 1016 KB Output is correct
12 Correct 39 ms 1024 KB Output is correct
13 Correct 316 ms 1016 KB Output is correct
14 Correct 208 ms 1016 KB Output is correct
15 Correct 282 ms 1152 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 217 ms 19960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 285 ms 1016 KB Output is correct
11 Correct 163 ms 1016 KB Output is correct
12 Correct 39 ms 1024 KB Output is correct
13 Correct 316 ms 1016 KB Output is correct
14 Correct 208 ms 1016 KB Output is correct
15 Correct 282 ms 1152 KB Output is correct
16 Runtime error 217 ms 19960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -