oj.uz

Submission #1020771

# Submission time Handle Problem Language Result Execution time Memory
1020771 2024-07-12T09:40:50 Z JakobZorz Werewolf (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory 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 -