Submission #590050

#	Time	Username	Problem	Language	Result	Execution time	Memory
590050		Dremix10	Werewolf (IOI18_werewolf)	C++17	15 / 100	4050 ms	36180 KiB

werewolf

#include "werewolf.h"
#include <iostream>
#include <numeric>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x) {}
    #define p2(x,y) {}
    #define pp(x) {}
    #define pv(x) {}
    #define ppv(x) {}
#endif
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 2e18;
const int MOD = 1e9+7;
//const int N = 3e5+1;

vector<int> par,siz,vis;


int find(int x){
    return (par[x] == x) ? x : par[x] = find(par[x]);
}

void join(int x, int y){
    x = find(x);
    y = find(y);
    if(x==y)return;
    if(siz[y] > siz[x])
        swap(x,y);
    par[y] = x;
    siz[x] += siz[y];
}

vector<vector<int> > a;
int use;
bool flag;
int l,r;


void dfs(int s){
    vis[s] = use;
    for(auto x : a[s]){
        if(use == 1 && x < l)continue;
        if(use == 2 && x > r)continue;

        if(!vis[x])dfs(x);
        if(vis[x] == 1 && use == 2){
            flag = true;
        }
    }

}

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
    par.resize(N);
    siz.resize(N);
    vis.resize(N);
    a.assign(N,vector<int>());
    
    int q = S.size();
    int m = X.size();

    int i,k;

    for(i=0;i<m;i++){
        int x = X[i], y = Y[i];
        a[x].push_back(y);
        a[y].push_back(x);
    }

    vector<int> ans;

    for(k=0;k<q;k++){
        int s = S[k], e = E[k];
        l = L[k];
        r = R[k];

        iota(all(par),0);
        fill(all(siz),1);
        fill(all(vis),0);

        use = 1;
        flag = false;
        dfs(s);

        use = 2;

        if(vis[e] == 1)flag = true;
        dfs(e);

        ans.push_back(flag);

    }


    return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51