Submission #313633

#	Time	Username	Problem	Language	Result	Execution time	Memory
313633		talant117408	Werewolf (IOI18_werewolf)	C++17	15 / 100	4061 ms	35544 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <ll, ll> pii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) (int)(v).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int N = 2e5+7;
vector <vector <int>> graph(N);
vector <int> eq, vis, belong, cluster, can, can2;
int n, q, clcnt;

void go(int v, int cond){
    vis[v] = 1;
    if(cluster[belong[v]] == 1){
        if(!cond) can[belong[v]] = 1;
        else can2[belong[v]] = 1;
    }
    
    for(auto to : graph[v]){
        if(!vis[to] && (cond != cluster[belong[to]])){
            go(to, cond);
        }
    }
}

void findcl(int v){
    cluster[clcnt] = eq[v];
    belong[v] = clcnt;
    vis[v] = 1;
    
    for(auto to : graph[v]){
        if(!vis[to] && eq[to] == eq[v]){
            findcl(to);
        }
    }
}

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 i, j;
    n = N, q = sz(S);
    vector <int> ans(q);
    
    for(i = 0; i < sz(X); i++){
        graph[X[i]].pb(Y[i]);
        graph[Y[i]].pb(X[i]);
    }
    
    for(j = 0; j < q; j++){
        eq = vis = belong = cluster = can = can2 = vector <int> (n);
        for(i = 0; i < n; i++){
            if(i < L[j]) eq[i] = 0;
            else if(i > R[j]) eq[i] = 2;
            else eq[i] = 1;
        }
        
        clcnt = 0;
        
        for(i = 0; i < n; i++){
            if(!vis[i]){
                findcl(i);
                clcnt++;
            }
        }
        
        if(cluster[belong[S[j]]] == 0 || cluster[belong[E[j]]] == 2){
            continue;
        }
        for(i = 0; i < n; i++) vis[i] = 0;
        go(S[j], 0);
        for(i = 0; i < n; i++) vis[i] = 0;
        go(E[j], 2);
        
        for(i = 0; i < clcnt; i++){
            if(can[i] && can2[i]){
                ans[j] = 1;
                break;
            }
        }
    }
    
    return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/

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