Submission #1020884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020884		JakobZorz	Werewolf (IOI18_werewolf)	C++17	15 / 100	4058 ms	88092 KiB

werewolf

#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]];
    /*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(n);
        for(int j=0;j<(int)line.size();j++){
            if(line[j]==E[i]){
                for(int k=j;k<(int)line.size()&&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: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51