oj.uz

Submission #600843

# Submission time Handle Problem Language Result Execution time Memory
600843 2022-07-21T08:15:34 Z enerelt14 Werewolf (IOI18_werewolf) C++14
15 / 100
 321 ms 19664 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
bool vis[3005], is[3005];
vector<int>adj[3005];
void dijkstra1(int s, int l){
    queue<int>pq;
    pq.push(s);
    while(!pq.empty()){
        int u=pq.front();
        pq.pop();
        vis[u]=1;
        for (int i=0;i<adj[u].size();i++){
            if (adj[u][i]<l || vis[adj[u][i]])continue;
            pq.push(adj[u][i]);
        }
        while(!pq.empty() && vis[pq.front()])pq.pop();
    }
}
void dijkstra2(int s, int r){
    queue<int>pq;
    pq.push(s);
    while(!pq.empty()){
        int u=pq.front();
        pq.pop();
        vis[u]=1;
        for (int i=0;i<adj[u].size();i++){
            if (adj[u][i]>r || vis[adj[u][i]])continue;
            pq.push(adj[u][i]);
        }
        while(!pq.empty() && vis[pq.front()])pq.pop();
    }
}
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
    for (int i=0;i<X.size();i++){
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }
    int Q=S.size();
    vector<int>ans;
    for (int j=0;j<Q;j++){
        ans.pb(0);
        if (S[j]<L[j] || E[j]>R[j])continue;
        for (int i=L[j];i<N;i++)vis[i]=0;
        dijkstra1(S[j], L[j]);
        for (int i=L[j];i<=R[j];i++)is[i]=vis[i];
        for (int i=0;i<=R[j];i++)vis[i]=0;
        dijkstra2(E[j], R[j]);
        for (int i=L[j];i<=R[j];i++){
            if (vis[i] && is[i]){
                ans[j]=1;
                break;
            }
        }
    }
    return ans;
}

Compilation message

werewolf.cpp: In function 'void dijkstra1(int, int)':
werewolf.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |         for (int i=0;i<adj[u].size();i++){
      |                      ~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void dijkstra2(int, int)':
werewolf.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int i=0;i<adj[u].size();i++){
      |                      ~^~~~~~~~~~~~~~
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:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i=0;i<X.size();i++){
      |                  ~^~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 270 ms 616 KB Output is correct
11 Correct 160 ms 632 KB Output is correct
12 Correct 19 ms 640 KB Output is correct
13 Correct 269 ms 608 KB Output is correct
14 Correct 178 ms 604 KB Output is correct
15 Correct 321 ms 812 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 137 ms 19664 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 270 ms 616 KB Output is correct
11 Correct 160 ms 632 KB Output is correct
12 Correct 19 ms 640 KB Output is correct
13 Correct 269 ms 608 KB Output is correct
14 Correct 178 ms 604 KB Output is correct
15 Correct 321 ms 812 KB Output is correct
16 Runtime error 137 ms 19664 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -