제출 #293959

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293959		shayan_p	늑대인간 (IOI18_werewolf)	C++17	100 / 100	1535 ms	151768 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<int> tmpv[maxn];
int pr[maxn];
bool seen[maxn];

int fnd(int u){
    return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
vector<pii> build_tree(vector<int> vec, vector<pii> ed){ // TLE?
    memset(pr, -1, sizeof pr);
    memset(seen, 0, sizeof seen);
    for(int u : vec){
	tmpv[u].clear();
    }
    for(pii p : ed){
	tmpv[p.F].PB(p.S);
	tmpv[p.S].PB(p.F);
    }
    vector<pii> ans;
    for(int u : vec){
	seen[u] = 1;
	for(int y : tmpv[u]){
	    if(!seen[y])
		continue;
	    y = fnd(y);
	    if(y == u)
		continue;
	    ans.PB({u, y});
	    pr[y] = u;
	}
    }
    assert(sz(ans) + 1 == sz(vec));
    return ans;
}

vector<int> v[maxn];
int segl[maxn], segr[maxn];

void prep(int u, int par = -1){
    static int C = 0;
    segl[u] = C++;
    for(int y : v[u])
	if(y != par)
	    prep(y, u);
    segr[u] = C;
}

int sp[20][maxn];

void prep2(int u, int par = -1){
    sp[0][u] = par;
    for(int i = 1; i < 20; i++)
	sp[i][u] = (sp[i-1][u] == -1 ? -1 : sp[i-1][sp[i-1][u]]);
    for(int y : v[u])
	if(y != par)
	    prep2(y, u);
}

set<int> st[maxn];
vector< pair<pii, int> > qur[maxn];
int ans[maxn];

void dfs(int u, int par = -1){
    st[u].insert(u);
    for(int y : v[u]){
	if(y != par){
	    dfs(y, u);
	    if(sz(st[u]) < sz(st[y]))
		swap(st[u], st[y]);
	    for(int x : st[y])
		st[u].insert(x);
	}
    }
    for(auto [seg, id] : qur[u]){
	auto it = st[u].lower_bound(seg.F);
	ans[id] = it != st[u].end() && (*it) < seg.S;
    }
}

vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    int q = sz(S), m = sz(X);
    vector<int> vec(n);
    iota(vec.begin(), vec.end(), 0);
    vector<pii> ed;
    for(int i = 0; i < m; i++)
	ed.PB({X[i], Y[i]});
    
    reverse(vec.begin(), vec.end());
    vector<pii> T1 = build_tree(vec, ed);
    reverse(vec.begin(), vec.end());
    vector<pii> T2 = build_tree(vec, ed);
    
    for(int i = 0; i < n; i++){
	v[i].clear();
    }
    for(int i = 0; i < n-1; i++){
	v[T2[i].F].PB(T2[i].S);
	v[T2[i].S].PB(T2[i].F);
    }
    prep(n-1);
    prep2(n-1);
    for(int i = 0; i < q; i++){
	int &u = E[i];
	for(int j = 19; j >= 0; j--){
	    if(sp[j][u] != -1 && sp[j][u] <= R[i])
		u = sp[j][u];
	}	
    }


    for(int i = 0; i < n; i++){
	v[i].clear();
    }
    for(int i = 0; i < n-1; i++){
	v[T1[i].F].PB(T1[i].S);
	v[T1[i].S].PB(T1[i].F);
    }
    prep2(0);
    for(int i = 0; i < q; i++){
	int &u = S[i];
	for(int j = 19; j >= 0; j--){
	    if(sp[j][u] != -1 && sp[j][u] >= L[i])
		u = sp[j][u];
	}
    }


    for(int i = 0; i < n; i++){
	v[i].clear();
    }
    for(int i = 0; i < n-1; i++){
	v[segl[ T1[i].F ]].PB(segl[ T1[i].S ]);
	v[segl[ T1[i].S ]].PB(segl[ T1[i].F ]);
    }
   
    for(int i = 0; i < q; i++){
	qur[ segl[S[i]] ].PB({{segl[E[i]], segr[E[i]]}, i});
    }
    dfs(segl[0]);

    vector<int> ret;
    for(int i = 0; i < q; i++){
	ret.PB(ans[i]);
    }
    return ret;
}

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