Submission #434138

#	Time	Username	Problem	Language	Result	Execution time	Memory
434138		vanic	Werewolf (IOI18_werewolf)	C++14	15 / 100	4069 ms	28512 KiB

werewolf

    #include "werewolf.h"
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <vector>
     
    using namespace std;
     
    const int maxn=2e5+5;
     
    struct union_find{
    	int kad[maxn];
    	int parent[maxn];
    	int sz[maxn];
    	union_find(){
    		for(int i=0; i<maxn; i++){
    			parent[i]=i;
    			sz[i]=1;
    			kad[i]=0;
    		}
    	}
    	int find(int x, int vrij){
    		if(kad[x]>vrij || parent[x]==x){
    			return x;
    		}
    		return find(parent[x], vrij);
    	}
    	void update(int x, int y, int vrij){
    		x=find(x, vrij);
    		y=find(y, vrij);
    		if(sz[x]>sz[y]){
    			swap(x, y);
    		}
    		parent[x]=y;
          	sz[y]+=sz[x];
    		kad[x]=vrij;
    	}
    	bool query(int x, int y, int vrij){
    		return find(x, vrij)==find(y, vrij);
    	}
    };
     
    //int pos1[maxn], pos2[maxn];
    vector < int > ms[maxn];
    vector < int > s, e, l, r;
    vector < int > sol;
    int n;
    /*
    bool cmp1(int a, int b){
    	return l[a]>l[b];
    }
     
    bool cmp2(int a, int b){
    	return r[a]<r[b];
    }
    */
    union_find U1, U2;
     
    void dodaj1(int x){
    	for(int i=0; i<(int)ms[x].size(); i++){
    		if(ms[x][i]<x){
    			if(!U1.query(x, ms[x][i], x+1)){
    				U1.update(x, ms[x][i], x+1);
    			}
    		}
    	}
    }
     
    void dodaj2(int x){
    	for(int i=0; i<(int)ms[x].size(); i++){
    		if(ms[x][i]>x){
    			if(!U2.query(x, ms[x][i], n-x)){
    				U2.update(x, ms[x][i], n-x);
    			}
    		}
    	}
    }
    	
    vector < int > check_validity(int N, vector < int > x, vector < int > y, vector < int > S, vector < int > E, vector < int > L, vector < int > R){
    	s=S;
    	e=E;
    	l=L;
    	r=R;
    	n=N;
    	int m=x.size();
    	for(int i=0; i<m; i++){
    		ms[x[i]].push_back(y[i]);
    		ms[y[i]].push_back(x[i]);
    	}
    	int q=s.size();
    	for(int i=0; i<n; i++){
    		dodaj1(i);
    		dodaj2(n-i-1);
    	}
    	bool p;
    	for(int i=0; i<q; i++){
    		p=1;
    		for(int j=l[i]; j<=r[i]; j++){
    			if(U1.query(e[i], j, r[i]+1) && U2.query(s[i], j, n-l[i])){
    				sol.push_back(1);
    				p=0;
    				break;
    			}
    		}
    		if(p){
    			sol.push_back(0);
    		}
    	}
    	return sol;
    }

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