oj.uz

답안 #759296

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
759296 2023-06-16T04:28:07 Z Khizri 늑대인간 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -