oj.uz

Submission #116224

# Submission time Handle Problem Language Result Execution time Memory
116224 2019-06-11T10:49:57 Z zubec Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 28216 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 200100;

vector <int> g[N];

int d[2][N];

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();
    std::vector<int> A(Q);

    for (int i = 0; i < X.size(); i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    for (int i = 0; i < Q; i++){
        for (int j = 0; j < N; j++){
            d[0][j] = d[1][j] = 1e9;
        }
        d[0][S[i]] = 0;
        queue <int> q;
        q.push(S[i]);
        while(!q.empty()){
            int v = q.front();
            q.pop();
            for (int j = 0; j < g[v].size(); j++){
                int to = g[v][j];
                if (L[i] <= to && d[0][v] + 1 < d[0][to]){
                    d[0][to] = d[0][v] + 1;
                    q.push(to);
                }
            }
        }
        d[1][E[i]] = 0;
        q.push(E[i]);
        while(!q.empty()){
            int v = q.front();
            q.pop();
            for (int j = 0; j < g[v].size(); j++){
                int to = g[v][j];
                if (to <= R[i] && d[1][v] + 1 < d[1][to]){
                    d[1][to] = d[1][v] + 1;
                    q.push(to);
                }
            }
        }
        bool bb = 0;
        for (int j = L[i]; j <= R[i]; j++){
            if (d[0][j] != 1e9 && d[1][j] != 1e9){
                bb = 1;
                break;
            }
        }
        A[i] = bb;
    }

    return A;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:17:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < X.size(); i++){
                     ~~^~~~~~~~~~
werewolf.cpp:31:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < g[v].size(); j++){
                             ~~^~~~~~~~~~~~~
werewolf.cpp:44:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < g[v].size(); j++){
                             ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 271 ms 5404 KB Output is correct
11 Correct 164 ms 5376 KB Output is correct
12 Correct 29 ms 5376 KB Output is correct
13 Correct 278 ms 5376 KB Output is correct
14 Correct 205 ms 5496 KB Output is correct
15 Correct 248 ms 5504 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Correct 6 ms 4992 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 271 ms 5404 KB Output is correct
11 Correct 164 ms 5376 KB Output is correct
12 Correct 29 ms 5376 KB Output is correct
13 Correct 278 ms 5376 KB Output is correct
14 Correct 205 ms 5496 KB Output is correct
15 Correct 248 ms 5504 KB Output is correct
16 Execution timed out 4091 ms 28216 KB Time limit exceeded
17 Halted 0 ms 0 KB -