제출 #585173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585173		20160161simone	늑대인간 (IOI18_werewolf)	C++14	15 / 100	4034 ms	16272 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll f[2][N];
enum state{ human,wolf };
ll Find(ll x,ll sat){
    if(f[sat][x]<0) return x;
    else return f[sat][x]=Find(f[sat][x],sat);
}
void Union(ll x,ll y,ll sat){
    x=Find(x,sat),y=Find(y,sat);
    if(x==y) return;
    f[sat][y]=x;
}

vector<int> check_validity(int n, vector<int> u, vector<int> v, vector<int> s, vector<int> e,vector<int> l, vector<int> r) {
    ll q = s.size(),m=u.size();
    vector<int> ans;
    for(ll kase=0;kase<q;kase++){

        for(ll i=0;i<n;i++) f[human][i]=f[wolf][i]=-1;

        for(ll i=0;i<m;i++){
            if(u[i]<=r[kase] && v[i]<=r[kase]) Union(u[i],v[i],wolf);
            if(u[i]>=l[kase] && v[i]>=l[kase]) Union(u[i],v[i],human);
        }
        ll flag=0;
        for(ll i=l[kase];i<=r[kase];i++){
            if(Find(s[kase],human)==Find(i,human) && Find(i,wolf)==Find(e[kase],wolf)){
                flag=1;
                break;
            }
        }

        // printf("%lld\nwolf:",kase);
        // for(ll i=0;i<n;i++){
        //     if(Find(s[kase],wolf)==Find(i,wolf)) printf("%lld ",i);
        // }cout<<endl;
        // printf("human:");
        // for(ll i=0;i<n;i++){
        //     if(Find(i,human)==Find(e[kase],human)) printf("%lld ",i);
        // }cout<<endl;

        ans.push_back(flag);
    }
    return ans;
}

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