oj.uz

Submission #81508

# Submission time Handle Problem Language Result Execution time Memory
81508 2018-10-25T07:23:54 Z zubec Werewolf (IOI18_werewolf) C++14
0 / 100
 4000 ms 30932 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) {
    for (int i = 0; i < N; i++){
        g[i].clear();
    }
    for (int i = 0; i < N-1; i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    vector <int> A;
    for (int ii = 0; ii < S.size(); ii++){
        int u = S[ii], v = E[ii];
        int l = L[ii], r = R[ii];
        for (int i = 0; i < N; i++){
            d[0][i] = d[1][i] = 1e9;
        }
        queue <int> q;
        if (u >= l){
            d[0][u] = 0;
            q.push(u);
        }
        while(!q.empty()){
            int v = q.front();
            q.pop();
            for (int i = 0; i < g[v].size(); i++){
                int to = g[v][i];
                if (to >= l && d[0][v] + 1 < d[0][to]){
                    d[0][to] = d[0][v] + 1;
                    q.push(to);
                }
            }
        }
        if (v <= r){
            d[1][v] = 0;
            q.push(v);
        }
        while(!q.empty()){
            int v = q.front();
            q.pop();
            for (int i = 0; i < g[v].size(); i++){
                int to = g[v][i];
                if (to <= r && d[1][v] + 1 < d[1][to]){
                    d[1][to] = d[1][v] + 1;
                    q.push(to);
                }
            }
        }
        int bb = 0;
        for (int i = l; i <= r; i++){
            if (d[0][i] != 1e9 && d[1][i] != 1e9){
                bb = 1;
                break;
            }
        }
        A.push_back(bb);
    }

    return A;

}

/**

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

*/

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:20:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int ii = 0; ii < S.size(); ii++){
                      ~~~^~~~~~~~~~
werewolf.cpp:34:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < g[v].size(); i++){
                             ~~^~~~~~~~~~~~~
werewolf.cpp:49:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < g[v].size(); i++){
                             ~~^~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -