Submission #139791

#	Time	Username	Problem	Language	Result	Execution time	Memory
139791		almogwald	Werewolf (IOI18_werewolf)	C++14	0 / 100	482 ms	91996 KiB

werewolf

#include <utility>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#include <iostream>
//#include "job.h"
#include "werewolf.h"
#define fori(i,n) for(int i=0;i<n;i++)
#define forn(i,n) for(int i=1;i<n;i++)
#define forib(i,n) for(int i=n-1;i>=0;i--)
#define fornb(i,n) for(int i=n-1;i>0;i--)
#define maxl 10000000000
#define con continue;
typedef long long lol;
using namespace std;
typedef vector<int> veci;
typedef pair<lol,lol> point;
lol sum=0;

#define k 20
veci check_validity(int n, veci X, veci Y,veci S, veci E,veci L,veci R) {
	vector<vector<int>> cons(n);
	int Q = S.size();
	veci A(Q);
	fori(i,X.size()){
		cons[X[i]].push_back(Y[i]);
		cons[Y[i]].push_back(X[i]);
	}
	int cur=0;
	fori(i,n){
		if(cons[i].size()==1){
			cur=i;
			break;
		}
	}
	int p=cur;
	veci ord;
	veci place(n);
	place[cur]=0;
	ord.push_back(cur);
	bool ok=true;
	while(ok){
		ok=false;
		fori(i,cons[cur].size()){
			if(cons[cur][i]!=p){
				ok=true;
				place[cons[cur][i]]=ord.size();
				ord.push_back(cons[cur][i]);
				p=cur;
				cur=cons[cur][i];
				break;
			}
		}
	}
	veci had;
	vector<veci> l1(k,veci(n));
	vector<veci> l2(k,veci(n));
	fori(i,n){
		while(!had.empty() && ord[had.back()]>ord[i]){
			had.pop_back();
		}
		l1[0][i]=i;
		if(had.size()){
			l1[0][i]=had.back();
		}
		forn(j,k){
			l1[j][i]=l1[j-1][l1[j-1][i]];
		}
	}
	had.resize(0);
	forib(i,n){
		while(!had.empty() && ord[had.back()]>ord[i]){
			had.pop_back();
		}
		l2[0][i]=i;
		if(had.size()){
			l2[0][i]=had.back();
		}
		forn(j,k){
			l2[j][i]=l2[j-1][l2[j-1][i]];
		}
	}
	had.resize(0);
	vector<veci> r1(k,veci(n));
	vector<veci> r2(k,veci(n));
	fori(i,n){
		while(!had.empty() && ord[had.back()]<ord[i]){
			had.pop_back();
		}
		r1[0][i]=i;
		if(had.size()){
			r1[0][i]=had.back();
		}
		forn(j,k){
			r1[j][i]=r1[j-1][r1[j-1][i]];
		}
	}
	had.resize(0);
	forib(i,n){
		while(!had.empty() && ord[had.back()]<ord[i]){
			had.pop_back();
		}
		r2[0][i]=i;
		if(had.size()){
			r2[0][i]=had.back();
		}
		forn(j,k){
			r2[j][i]=r2[j-1][r2[j-1][i]];
		}
	}
	fori(p,Q) {
		if(S[p]<L[p]|| E[p]>R[p]){
			con
		}
		int poss=place[S[p]];
		int pose=place[E[p]];
		if(poss<pose){
			int m=19;
			if(ord[r2[m][poss]]<=R[p]){
				A[p]=1;
				con
			}
			while(m>=0){
				if(ord[r2[m][poss]]<=R[p]){
					poss=r2[m][poss];
					con
				}
				m--;
			}
			poss=r2[0][poss];
			m=19;
			if(ord[l1[m][pose]]>=L[p]){
				A[p]=1;
				con
			}
			while(m>=0){
				if(ord[l1[m][pose]]>=L[p]){
					pose=l1[m][pose];
					con
				}
				m--;
			}
			pose=l1[0][pose];
			if(pose+1<poss){
				A[p]=1;
			}
		}else{
			int m=19;
			if(ord[r1[m][poss]]<=R[p]){
				A[p]=1;
				con
			}
			while(m>=0){
				if(ord[r1[m][poss]]<=R[p]){
					poss=r1[m][poss];
					con
				}
				m--;
			}
			poss=r1[0][poss];
			m=19;
			if(ord[l2[m][pose]]>=L[p]){
				A[p]=1;
				con
			}
			while(m>=0){
				if(ord[l2[m][pose]]>=L[p]){
					pose=l2[m][pose];
					con
				}
				m--;
			}
			pose=l2[0][pose];
			if(poss+1<pose){
				A[p]=1;
			}
		}
	}
	return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'veci check_validity(int, veci, veci, veci, veci, veci, veci)':
werewolf.cpp:9:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
werewolf.cpp:26:7:
  fori(i,X.size()){
       ~~~~~~~~~~                
werewolf.cpp:26:2: note: in expansion of macro 'fori'
  fori(i,X.size()){
  ^~~~
werewolf.cpp:9:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fori(i,n) for(int i=0;i<n;i++)
werewolf.cpp:45:8:
   fori(i,cons[cur].size()){
        ~~~~~~~~~~~~~~~~~~       
werewolf.cpp:45:3: note: in expansion of macro 'fori'
   fori(i,cons[cur].size()){
   ^~~~

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