oj.uz

Submission #425640

# Submission time Handle Problem Language Result Execution time Memory
425640 2021-06-13T09:27:14 Z TryMax Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 31580 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#ifdef LOCAL
    #include "grader.cpp"
#endif // LOCAL

#define pb push_back

using namespace std;

const int N = 2e5 + 10;

int canh[N], canw[N];
vector<int> a[N];

void dfs_l(int u, int num){
    canw[u] = 1;
    for(auto v : a[u])
        if(canw[v] == 0 && v <= num)
            dfs_l(v, num);
}

void dfs_g(int u, int num){
    canh[u] = 1;
    for(auto v : a[u])
        if(canh[v] == 0 && v >= num)
            dfs_g(v, num);
}

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 = s.size();
    int m = x.size();
    vector<int> ans;
    ans.resize(q);
    for(int i = 0; i < m; ++i){
        a[x[i]].pb(y[i]);
        a[y[i]].pb(x[i]);
    }
    for(int i = 0; i < q; ++i){
        for(int j = 0; j < n; ++j)
            canh[j] = canw[j] = 0;
        dfs_g(s[i], l[i]);
        dfs_l(e[i], r[i]);
        bool f = false;
        for(int j = l[i]; j <= r[i]; ++j)
            f |= (canh[j] && canw[j]);
        ans[i] = f;
    }
    return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 5004 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4996 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 5004 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4996 KB Output is correct
10 Correct 287 ms 5376 KB Output is correct
11 Correct 165 ms 5368 KB Output is correct
12 Correct 26 ms 5396 KB Output is correct
13 Correct 307 ms 5392 KB Output is correct
14 Correct 229 ms 5352 KB Output is correct
15 Correct 264 ms 5500 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 4 ms 5004 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4996 KB Output is correct
10 Correct 287 ms 5376 KB Output is correct
11 Correct 165 ms 5368 KB Output is correct
12 Correct 26 ms 5396 KB Output is correct
13 Correct 307 ms 5392 KB Output is correct
14 Correct 229 ms 5352 KB Output is correct
15 Correct 264 ms 5500 KB Output is correct
16 Execution timed out 4102 ms 31580 KB Time limit exceeded
17 Halted 0 ms 0 KB -