Submission #1020855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020855		JakobZorz	Werewolf (IOI18_werewolf)	C++17	0 / 100	4058 ms	524288 KiB

werewolf

#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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51