oj.uz

Submission #982117

# Submission time Handle Problem Language Result Execution time Memory
982117 2024-05-13T21:17:11 Z mariaclara Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 25736 KB 
#include "werewolf.h"
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
const int VAL = 500;
const int MAXN = 2e5+5;
#define pb push_back
#define fr first
#define sc second

bool vis1[MAXN], vis2[MAXN];
vector<int> edges[MAXN];

void dfs1(int x, int L) {
    vis1[x] = 1;
    for(int viz : edges[x])
        if(viz >= L and !vis1[viz]) dfs1(viz, L);
}

void dfs2(int x, int R) {
    vis2[x] = 1;
    for(int viz : edges[x])
        if(viz <= R and !vis2[viz]) dfs2(viz, R);
}

vector<int> check_validity(int n, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int q = (int)S.size();

    for(int i = 0; i < (int)X.size(); i++) {
        edges[X[i]].pb(Y[i]);
        edges[Y[i]].pb(X[i]);
    }

    vector<int> ans(q);
    for(int i = 0; i < q; i++) {
        fill(vis1, vis1+n, 0);
        fill(vis2, vis2+n, 0);
        dfs1(S[i], L[i]);
        dfs2(E[i], R[i]);
        for(int j = 0; j < n; j++)
            if(vis1[j] and vis2[j]) ans[i] = 1;
    }

    return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4960 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 198 ms 5504 KB Output is correct
11 Correct 111 ms 5468 KB Output is correct
12 Correct 21 ms 5720 KB Output is correct
13 Correct 222 ms 5492 KB Output is correct
14 Correct 148 ms 5472 KB Output is correct
15 Correct 177 ms 5620 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4017 ms 25736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4960 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 198 ms 5504 KB Output is correct
11 Correct 111 ms 5468 KB Output is correct
12 Correct 21 ms 5720 KB Output is correct
13 Correct 222 ms 5492 KB Output is correct
14 Correct 148 ms 5472 KB Output is correct
15 Correct 177 ms 5620 KB Output is correct
16 Execution timed out 4017 ms 25736 KB Time limit exceeded
17 Halted 0 ms 0 KB -