oj.uz

Submission #532208

# Submission time Handle Problem Language Result Execution time Memory
532208 2022-03-02T13:34:40 Z nicholask Werewolf (IOI18_werewolf) C++14
100 / 100
 1409 ms 188892 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
using namespace std;
using pii=pair <int,int>;
int dsu[400040];
void init(int sz){
    for (int i=0; i<sz; i++) dsu[i]=i;
}
int prt(int node){
    if (dsu[node]==node) return node;
    return dsu[node]=prt(dsu[node]);
}
void unn(int u,int v){
    u=prt(u); v=prt(v);
    if (u==v) return;
    dsu[u]=dsu[v];
}
bool cmp1(pii a,pii b){
    return min(a.x,a.y)>min(b.x,b.y);
}
bool cmp2(pii a,pii b){
    return max(a.x,a.y)<max(b.x,b.y);
}
vector <int> humanGraph[400040],wolfGraph[400040];
int humanP[400040],wolfP[400040]; //leaves permutation
pii humanR[400040],wolfR[400040]; //range
int tme;
int humanval[400040],wolfval[400040];
int humanlca[400040][19],wolflca[400040][19];
pii humanDfs(int cur,int prv){
    humanlca[cur][0]=prv;
    if (humanGraph[cur].empty()){
        humanP[tme]=cur;
        tme++;
        return humanR[cur]={tme-1,tme-1};
    }
    vector <pii> ranges;
    for (auto i:humanGraph[cur]) ranges.pb(humanDfs(i,cur));
    sort(ranges.begin(),ranges.end());
    return humanR[cur]={ranges.front().x,ranges.back().y};
}
pii wolfDfs(int cur,int prv){
    wolflca[cur][0]=prv;
    if (wolfGraph[cur].empty()){
        wolfP[tme]=cur;
        tme++;
        return wolfR[cur]={tme-1,tme-1};
    }
    vector <pii> ranges;
    for (auto i:wolfGraph[cur]) ranges.pb(wolfDfs(i,cur));
    sort(ranges.begin(),ranges.end());
    return wolfR[cur]={ranges.front().x,ranges.back().y};
}
struct wavelet{
	int lo,hi;
	wavelet *lhs=0,*rhs=0;
	vector <int> b;
	wavelet(vector<int>v):wavelet(v.begin(),v.end(),*min_element(v.begin(),v.end()),*max_element(v.begin(),v.end())){};
	~wavelet(){
		if (lhs) delete lhs;
		if (rhs) delete rhs;
	}
	template <typename T> wavelet(T from,T to,int lo_,int hi_){
		lo=lo_;
		hi=hi_;
		if (from>=to||lo==hi) return;
		int mi=lo+(hi-lo)/2;
		auto f=[&](int r){
			return r<=mi;
		};
		b.reserve(to-from+1);
		b.push_back(0);
		for (auto it=from; it!=to; it++) b.push_back(b.back()+f(*it));
		auto mit=stable_partition(from,to,f);
		lhs=new wavelet(from,mit,lo,mi);
		rhs=new wavelet(mit,to,mi+1,hi);
	}
	int lte(int l,int r,int k){
		if (l>r||k<lo) return 0;
		if (hi<=k) return r-l+1;
		return this->lhs->lte(b[l],b[r+1]-1,k)+this->rhs->lte(l-b[l],r-b[r+1],k);
	}
};
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 m=X.size();
    vector <pii> edge;
    for (int i=0; i<m; i++) edge.pb({X[i],Y[i]});
    sort(edge.begin(),edge.end(),cmp1);
    init(2*N);
    int cur=N;
    for (int i=0; i<N; i++) humanval[i]=i;
    for (auto i:edge){
        if (prt(i.x)==prt(i.y)) continue;
        humanGraph[cur].pb(prt(i.x));
        humanGraph[cur].pb(prt(i.y));
        humanval[cur]=min(humanval[prt(i.x)],humanval[prt(i.y)]);
        unn(i.x,cur);
        unn(i.y,cur);
        cur++;
    }
    tme=0;
    for (int i=0; i<2*N; i++){
        for (int j=0; j<19; j++) humanlca[i][j]=-1;
    }
    humanDfs(cur-1,-1);
    for (int j=1; j<19; j++){
        for (int i=0; i<2*N; i++){
            if (humanlca[i][j-1]==-1) humanlca[i][j]=-1;
            else humanlca[i][j]=humanlca[humanlca[i][j-1]][j-1];
        }
    }
    sort(edge.begin(),edge.end(),cmp2);
    init(2*N);
    cur=N;
    for (int i=0; i<N; i++) wolfval[i]=i;
    for (int i=N; i<2*N; i++) wolfval[i]=1e9; 
    for (auto i:edge){
        if (prt(i.x)==prt(i.y)) continue;
        wolfGraph[cur].pb(prt(i.x));
        wolfGraph[cur].pb(prt(i.y));
        wolfval[cur]=max(wolfval[prt(i.x)],wolfval[prt(i.y)]);
        unn(i.x,cur);
        unn(i.y,cur);
        cur++;
    }
    tme=0;
    for (int i=0; i<2*N; i++){
        for (int j=0; j<19; j++) wolflca[i][j]=-1;
    }
    wolfDfs(cur-1,-1);
    for (int j=1; j<19; j++){
        for (int i=0; i<2*N; i++){
            if (wolflca[i][j-1]==-1) wolflca[i][j]=-1;
            else wolflca[i][j]=wolflca[wolflca[i][j-1]][j-1];
        }
    }
    vector <int> poshuman(N);
    for (int i=0; i<N; i++) poshuman[humanP[i]]=i;
    vector <int> r(N);
    for (int i=0; i<N; i++) r[i]=poshuman[wolfP[i]];
    wavelet tree(r);
    vector <int> ans;
    for (int Q=0; Q<S.size(); Q++){
        int st=S[Q],en=E[Q];
        if (humanval[st]<L[Q]||wolfval[en]>R[Q]){
            ans.pb(-1);
            continue;
        }
        for (int i=18; i>=0; i--){
            if (humanlca[st][i]==-1) continue;
            if (humanval[humanlca[st][i]]>=L[Q]) st=humanlca[st][i];
        }
        for (int i=18; i>=0; i--){
            if (wolflca[en][i]==-1) continue;
            if (wolfval[wolflca[en][i]]<=R[Q]) en=wolflca[en][i];
        }
        if (tree.lte(wolfR[en].x,wolfR[en].y,humanR[st].y)!=tree.lte(wolfR[en].x,wolfR[en].y,humanR[st].x-1)) ans.pb(1);
        else ans.pb(0);
    }
    return ans;
}
/*
signed main(){
    int N,M,Q;
    cin>>N>>M>>Q;
    vector <int> X,Y,S,E,L,R;
    for (int i=0; i<M; i++){
        int xj,yj;
        cin>>xj>>yj;
        X.pb(xj);
        Y.pb(yj);
    }
    for (int i=0; i<Q; i++){
        int si,ei,li,ri;
        cin>>si>>ei>>li>>ri;
        S.push_back(si);
        E.push_back(ei);
        L.push_back(li);
        R.push_back(ri);
    }
    vector <int> ans=check_validity(N,X,Y,S,E,L,R);
    for (int i:ans) cout<<i<<' ';
}
*/

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:146:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for (int Q=0; Q<S.size(); Q++){
      |                   ~^~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19148 KB Output is correct
2 Correct 11 ms 19136 KB Output is correct
3 Correct 10 ms 19096 KB Output is correct
4 Correct 10 ms 19088 KB Output is correct
5 Correct 10 ms 19220 KB Output is correct
6 Correct 10 ms 19216 KB Output is correct
7 Correct 10 ms 19148 KB Output is correct
8 Correct 10 ms 19148 KB Output is correct
9 Correct 10 ms 19148 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19148 KB Output is correct
2 Correct 11 ms 19136 KB Output is correct
3 Correct 10 ms 19096 KB Output is correct
4 Correct 10 ms 19088 KB Output is correct
5 Correct 10 ms 19220 KB Output is correct
6 Correct 10 ms 19216 KB Output is correct
7 Correct 10 ms 19148 KB Output is correct
8 Correct 10 ms 19148 KB Output is correct
9 Correct 10 ms 19148 KB Output is correct
10 Correct 18 ms 21416 KB Output is correct
11 Correct 21 ms 21528 KB Output is correct
12 Correct 16 ms 21324 KB Output is correct
13 Correct 18 ms 21536 KB Output is correct
14 Correct 17 ms 21532 KB Output is correct
15 Correct 18 ms 21452 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 169628 KB Output is correct
2 Correct 1272 ms 179148 KB Output is correct
3 Correct 1043 ms 173080 KB Output is correct
4 Correct 877 ms 170244 KB Output is correct
5 Correct 878 ms 170200 KB Output is correct
6 Correct 862 ms 169872 KB Output is correct
7 Correct 718 ms 169688 KB Output is correct
8 Correct 1257 ms 179032 KB Output is correct
9 Correct 746 ms 173064 KB Output is correct
10 Correct 596 ms 170324 KB Output is correct
11 Correct 627 ms 170060 KB Output is correct
12 Correct 672 ms 169896 KB Output is correct
13 Correct 1211 ms 179176 KB Output is correct
14 Correct 1171 ms 179080 KB Output is correct
15 Correct 1142 ms 179344 KB Output is correct
16 Correct 1165 ms 179128 KB Output is correct
17 Correct 737 ms 169812 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19148 KB Output is correct
2 Correct 11 ms 19136 KB Output is correct
3 Correct 10 ms 19096 KB Output is correct
4 Correct 10 ms 19088 KB Output is correct
5 Correct 10 ms 19220 KB Output is correct
6 Correct 10 ms 19216 KB Output is correct
7 Correct 10 ms 19148 KB Output is correct
8 Correct 10 ms 19148 KB Output is correct
9 Correct 10 ms 19148 KB Output is correct
10 Correct 18 ms 21416 KB Output is correct
11 Correct 21 ms 21528 KB Output is correct
12 Correct 16 ms 21324 KB Output is correct
13 Correct 18 ms 21536 KB Output is correct
14 Correct 17 ms 21532 KB Output is correct
15 Correct 18 ms 21452 KB Output is correct
16 Correct 774 ms 169628 KB Output is correct
17 Correct 1272 ms 179148 KB Output is correct
18 Correct 1043 ms 173080 KB Output is correct
19 Correct 877 ms 170244 KB Output is correct
20 Correct 878 ms 170200 KB Output is correct
21 Correct 862 ms 169872 KB Output is correct
22 Correct 718 ms 169688 KB Output is correct
23 Correct 1257 ms 179032 KB Output is correct
24 Correct 746 ms 173064 KB Output is correct
25 Correct 596 ms 170324 KB Output is correct
26 Correct 627 ms 170060 KB Output is correct
27 Correct 672 ms 169896 KB Output is correct
28 Correct 1211 ms 179176 KB Output is correct
29 Correct 1171 ms 179080 KB Output is correct
30 Correct 1142 ms 179344 KB Output is correct
31 Correct 1165 ms 179128 KB Output is correct
32 Correct 737 ms 169812 KB Output is correct
33 Correct 1052 ms 172072 KB Output is correct
34 Correct 392 ms 49148 KB Output is correct
35 Correct 1301 ms 178156 KB Output is correct
36 Correct 976 ms 171160 KB Output is correct
37 Correct 1231 ms 176764 KB Output is correct
38 Correct 1058 ms 172384 KB Output is correct
39 Correct 1266 ms 188576 KB Output is correct
40 Correct 1049 ms 182116 KB Output is correct
41 Correct 940 ms 175476 KB Output is correct
42 Correct 710 ms 171120 KB Output is correct
43 Correct 1409 ms 183580 KB Output is correct
44 Correct 1179 ms 176584 KB Output is correct
45 Correct 877 ms 188892 KB Output is correct
46 Correct 1058 ms 188596 KB Output is correct
47 Correct 1160 ms 179300 KB Output is correct
48 Correct 1162 ms 179036 KB Output is correct
49 Correct 1182 ms 179376 KB Output is correct
50 Correct 1162 ms 179112 KB Output is correct
51 Correct 942 ms 182860 KB Output is correct
52 Correct 962 ms 182988 KB Output is correct