oj.uz

Submission #759296

# Submission time Handle Problem Language Result Execution time Memory
759296 2023-06-16T04:28:07 Z Khizri Werewolf (IOI18_werewolf) C++17
15 / 100
 198 ms 27972 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=3000+5;
int n,q,x[mxn],y[mxn],a[mxn],b[mxn],color[mxn],color2[mxn];
vector<int>vt[mxn];
void dfs(int u,int l,int r){
    if(u<l||u>r) return;
    color[u]=1;
    for(int v:vt[u]){
        if(!color[v]&&v>=l&&v<=r){
            dfs(v,l,r);
        }
    }
}
void dfs2(int u,int l,int r){
    if(u<l||u>r) return;
    color2[u]=1;
    for(int v:vt[u]){
        if(!color2[v]&&v>=l&&v<=r){
            dfs2(v,l,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) {
    n=N;
    q=S.size();
    for(int i=0;i<X.size();i++){
        vt[X[i]+1].pb(Y[i]+1);
        vt[Y[i]+1].pb(X[i]+1);
    }
    for(int i=0;i<S.size();i++){
        x[i+1]=S[i]+1;
        y[i+1]=E[i]+1;
        a[i+1]=L[i]+1;
        b[i+1]=R[i]+1;
    }
    vector<int>ans;
    for(int i=1;i<=q;i++){
        memset(color,0,sizeof(color));
        memset(color2,0,sizeof(color2));
        dfs(x[i],a[i],n);
        dfs2(y[i],1,b[i]);
        int ok=0;
        for(int j=a[i];j<=b[i];j++){
            if(color[j]&&color2[j]){
                ok=1;
                break;
            }
        }
        if(ok){
            ans.pb(1);
        }
        else{
            ans.pb(0);
        }
    }
    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
*/

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:41:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<X.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<S.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 368 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 1 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 368 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 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 182 ms 804 KB Output is correct
11 Correct 107 ms 724 KB Output is correct
12 Correct 12 ms 912 KB Output is correct
13 Correct 198 ms 824 KB Output is correct
14 Correct 115 ms 768 KB Output is correct
15 Correct 178 ms 964 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 27972 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 368 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 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 182 ms 804 KB Output is correct
11 Correct 107 ms 724 KB Output is correct
12 Correct 12 ms 912 KB Output is correct
13 Correct 198 ms 824 KB Output is correct
14 Correct 115 ms 768 KB Output is correct
15 Correct 178 ms 964 KB Output is correct
16 Runtime error 94 ms 27972 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -