oj.uz

Submission #1020855

# Submission time Handle Problem Language Result Execution time Memory
1020855 2024-07-12T10:31:37 Z JakobZorz Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 524288 KB 
#include"werewolf.h"
#include<queue>
#include<iostream>
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>comp(n);
    vector<vector<int>>comps(n);
    
    for(int i=0;i<n;i++){
        comps[i]={i};
        for(int ne:nodes[i]){
            if(ne>i)
                continue;
            comps[i].insert(comps[i].end(),comps[comp[ne]].begin(),comps[comp[ne]].end());
            comps[i].push_back(i);
        }
        for(int j:comps[i])
            comp[j]=i;
    }
    vector<int>line=comps[comp[0]];
    for(int i:line)
        cout<<i<<" ";
    cout<<"\n";
    
    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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 434 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 434 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 434 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -