oj.uz

Submission #1020874

# Submission time Handle Problem Language Result Execution time Memory
1020874 2024-07-12T10:42:10 Z JakobZorz Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 85552 KB 
#include"werewolf.h"
#include<queue>
#include<iostream>
#include<set>
using namespace std;

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

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};
        set<int>to_add;
        for(int ne:nodes[i]){
            if(ne>i)
                continue;
            to_add.insert(comp[ne]);
        }
        for(int j:to_add){
            comps[i].insert(comps[i].end(),comps[j].begin(),comps[j].end());
            comps[i].push_back(i);
        }
        for(int j:comps[i])
            comp[j]=i;
    }
    vector<int>line=comps[comp[0]];
    
    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]);
        vector<bool>v2(n);
        for(int j=0;j<(int)line.size();j++){
            if(line[j]==E[i]){
                for(int k=j;k<n&&line[k]<=R[i];k++)
                    v2[line[k]]=true;
                for(int k=j;k>=0&&line[k]<=R[i];k--)
                    v2[line[k]]=true;
                break;
            }
        }
        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 Correct 3 ms 5208 KB Output is correct
2 Incorrect 3 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Incorrect 3 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Incorrect 3 ms 4956 KB Output isn't correct
3 Halted 0 ms 0 KB -