oj.uz

Submission #434138

# Submission time Handle Problem Language Result Execution time Memory
434138 2021-06-20T15:30:38 Z vanic Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 28512 KB 
    #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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 7 ms 9608 KB Output is correct
5 Correct 7 ms 9676 KB Output is correct
6 Correct 6 ms 9668 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 7 ms 9692 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 7 ms 9608 KB Output is correct
5 Correct 7 ms 9676 KB Output is correct
6 Correct 6 ms 9668 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 7 ms 9692 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 35 ms 10004 KB Output is correct
11 Correct 41 ms 9976 KB Output is correct
12 Correct 70 ms 9968 KB Output is correct
13 Correct 23 ms 10004 KB Output is correct
14 Correct 28 ms 9984 KB Output is correct
15 Correct 137 ms 10052 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4069 ms 28512 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 7 ms 9608 KB Output is correct
5 Correct 7 ms 9676 KB Output is correct
6 Correct 6 ms 9668 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 7 ms 9692 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 35 ms 10004 KB Output is correct
11 Correct 41 ms 9976 KB Output is correct
12 Correct 70 ms 9968 KB Output is correct
13 Correct 23 ms 10004 KB Output is correct
14 Correct 28 ms 9984 KB Output is correct
15 Correct 137 ms 10052 KB Output is correct
16 Execution timed out 4069 ms 28512 KB Time limit exceeded
17 Halted 0 ms 0 KB -