oj.uz

답안 #1020771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1020771 2024-07-12T09:40:50 Z JakobZorz 늑대인간 (IOI18_werewolf) C++17
15 / 100
 4000 ms 29908 KB 
#include"werewolf.h"
#include<queue>
using namespace std;

int n,m,q;
vector<int>nodes[200000];

vector<bool>reachable1(int s,int t){
    vector<bool>vis(n);
    queue<int>q;
    q.push(s);
    while(q.size()){
        int node=q.front();
        q.pop();
        if(vis[node]||node>t)
            continue;
        vis[node]=true;
        for(int ne:nodes[node])
            q.push(ne);
    }
    return vis;
}

vector<bool>reachable2(int s,int t){
    vector<bool>vis(n);
    queue<int>q;
    q.push(s);
    while(q.size()){
        int node=q.front();
        q.pop();
        if(vis[node]||node<t)
            continue;
        vis[node]=true;
        for(int ne:nodes[node])
            q.push(ne);
    }
    return vis;
}

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;
    m=(int)X.size();
    q=(int)S.size();
    for(int i=0;i<n;i++){
        nodes[i].clear();
    }
    for(int i=0;i<m;i++){
        nodes[X[i]].push_back(Y[i]);
        nodes[Y[i]].push_back(X[i]);
    }
    
    vector<int>res(q);
    
    for(int i=0;i<q;i++){
        vector<bool>v1=reachable2(S[i],L[i]);
        vector<bool>v2=reachable1(E[i],R[i]);
        for(int j=0;j<n;j++)
            if(v1[j]&&v2[j])
                res[i]=1;
    }
    
    return res;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4992 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4888 KB Output is correct
9 Correct 2 ms 5116 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4992 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4888 KB Output is correct
9 Correct 2 ms 5116 KB Output is correct
10 Correct 251 ms 5468 KB Output is correct
11 Correct 132 ms 5468 KB Output is correct
12 Correct 15 ms 5468 KB Output is correct
13 Correct 244 ms 5468 KB Output is correct
14 Correct 143 ms 5468 KB Output is correct
15 Correct 196 ms 5464 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4030 ms 29908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4992 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4888 KB Output is correct
9 Correct 2 ms 5116 KB Output is correct
10 Correct 251 ms 5468 KB Output is correct
11 Correct 132 ms 5468 KB Output is correct
12 Correct 15 ms 5468 KB Output is correct
13 Correct 244 ms 5468 KB Output is correct
14 Correct 143 ms 5468 KB Output is correct
15 Correct 196 ms 5464 KB Output is correct
16 Execution timed out 4030 ms 29908 KB Time limit exceeded
17 Halted 0 ms 0 KB -