Submission #996868

#	Time	Username	Problem	Language	Result	Execution time	Memory
996868		errorgorn	Spy 3 (JOI24_spy3)	C++17	94 / 100	118 ms	81524 KiB

Aoi

#include "Aoi.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

namespace {

int n,m,q,k;

vector<ii> al[20005];
int w[20005];
int hidden[20005];

vector<ii> al2[20005];
ii pp[20005];

int d[20005];

int typ[20005];

int CNT=2;
int ID[1<<16];

string bs;
int inf[305];

int CNT2=0;
int posq[35];

void dfs(int i){
	bool f=false;
	if (ID[typ[i]]==-1){
		ID[typ[i]]=CNT++;
		f=true;
		bs+="0";
	}
	
	if (n<=i){
		//cout<<i<<" "<<ID[typ[i]]<<endl;
		posq[i-n]=CNT2++;
	}
	
	for (auto [it,id]:al2[i]) if ((typ[it])&1){
		if (typ[it]){
			dfs(it);
			if (hidden[id]!=-1) inf[hidden[id]]=ID[typ[it]];
			//if (typ[it]!=typ[i]) cout<<"? "<<ID[typ[i]]<<" "<<ID[typ[it]]<<endl;
		}
	}
	
	for (auto [it,id]:al2[i]) if ((~typ[it])&1){
		if (typ[it]){
			dfs(it);
			if (hidden[id]!=-1) inf[hidden[id]]=ID[typ[it]];
			//if (typ[it]!=typ[i]) cout<<"? "<<ID[typ[i]]<<" "<<ID[typ[it]]<<endl;
		}
	}
	
	if (f) bs+="1";
}

}  // namespace

std::string aoi(signed N, signed M, signed Q, signed K, std::vector<signed> A,
                std::vector<signed> B, std::vector<long long> C,
                std::vector<signed> T, std::vector<signed> X) {


	n=N,m=M,q=Q,k=K;
	
	rep(x,0,m){
		al[A[x]].pub({B[x],x});
		al[B[x]].pub({A[x],x});
		w[x]=C[x];
	}
	
	memset(hidden,-1,sizeof(hidden));
	rep(x,0,k) hidden[X[x]]=x;
	
	priority_queue<ii,vector<ii>,greater<ii> > pq;
	
	memset(d,63,sizeof(d));
	
	d[0]=0;
	pq.push({d[0],0});
	
	while (!pq.empty()){
		int u,ww; tie(ww,u)=pq.top(); pq.pop();
		
		if (d[u]!=ww) continue;
		
		for (auto [it,id]:al[u]) if (d[it]>ww+w[id]){
			d[it]=ww+w[id];
			pq.push({d[it],it});
			pp[it]={u,id};
		}
	}
	
	rep(x,1,n) al2[pp[x].fi].pub({x,pp[x].se});
	
	rep(x,0,q){
		int curr=T[x];
		
		while (curr){
			typ[curr]|=1<<x;
			curr=pp[curr].fi;
		}
		
		al2[T[x]].pub({n+x,20004});
		typ[n+x]=1<<x;
	}
	
	memset(ID,-1,sizeof(ID));
	typ[0]=(1<<q)-1;
	ID[(1<<q)-1]=1;
	
	dfs(0);
	
	//rep(x,0,n) cout<<typ[x]<<" "; cout<<endl;
	//rep(x,0,k) cout<<inf[x]<<" "; cout<<endl;
	
	string s;
	rep(x,0,k){
		rep(i,0,5) s+='0'+((inf[x]>>i)&1);
	}
	
	rep(x,1,q){
		//cout<<d[T[x]]<<endl;
		rep(i,0,4) s+='0'+((posq[x]>>i)&1);
	}
	
	if (bs=="") bs="01";
	return s+bs.substr(1,sz(bs)-2);
}

Bitaro

#include "Bitaro.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

namespace {

int n,m,q,k;

vector<ii> al[10005];
int w[20005];
vector<int> imp;
int rit[10005];

int d[610][10005];
ii pp[610][10005];

void add(int u){
	int i=sz(imp);
	rit[u]=i;
	imp.pub(u);
	
	priority_queue<ii,vector<ii>,greater<ii> > pq;
		
	memset(d[i],63,sizeof(d[i]));
	
	d[i][u]=0;
	pq.push({d[i][u],u});
	
	while (!pq.empty()){
		int u,ww; tie(ww,u)=pq.top(); pq.pop();
		
		if (d[i][u]!=ww) continue;
		
		for (auto [it,id]:al[u]) if (d[i][it]>ww+w[id]){
			d[i][it]=ww+w[id];
			pq.push({d[i][it],it});
			pp[i][it]={u,id};
		}
	}
}

int inf[305];
int sp[50];

ii PP[10005]; //this guys contains the actual answers

int RR[50];

}  // namespace

void bitaro(signed N, signed M, signed Q, signed K, std::vector<signed> A, std::vector<signed> B,
            std::vector<long long> C, std::vector<signed> T, std::vector<signed> X,
            std::string s) {
				
	
	n=N,m=M,q=Q,k=K;
	
	rep(x,0,m) if (C[x]!=-1){
		al[A[x]].pub({B[x],x});
		al[B[x]].pub({A[x],x});
		w[x]=C[x];
	}
	
	memset(rit,-1,sizeof(rit));
	
	add(0);
	
	rep(x,0,k){
		rep(i,0,5) if (s[x*5+i]=='1') inf[x]+=1<<i; 
	}
	
	int currn=2;
	vector<int> stk={1};
	
	string bs="0"+s.substr(k*5+(q-1)*4,sz(s)-(k*5+(q-1)*4))+"1";
	
	sp[1]=0;
	
	for (auto it:bs){
		if (it=='0'){
			sp[currn]=stk.back();
			stk.pub(currn++);
		}
		else{
			stk.pob();
		}
	}
	
	vector<int> LL;
	rep(x,1,currn){
		bool leaf=true;
		rep(y,1,currn) if (sp[y]==x) leaf=false;
		if (leaf) LL.pub(x);
	}
	
	//for (auto it:LL) cout<<it<<" "; cout<<endl;
	
	RR[0]=0;
	add(0);
	
	rep(x,1,currn){
		set<int> st;
		rep(y,0,k) if (inf[y]==x) st.insert(y);
		
		int R=RR[sp[x]];
		
		while (!st.empty()){
			int mn=1e18;
			for (auto it:st){
				mn=min(mn,d[rit[R]][A[X[it]]]);
				mn=min(mn,d[rit[R]][B[X[it]]]);
			}
			
			for (auto it:st){
				if (mn==d[rit[R]][A[X[it]]]){
					int curr=A[X[it]];
					while (curr!=R){
						PP[curr]={pp[rit[R]][curr].fi,pp[rit[R]][curr].se};
						curr=pp[rit[R]][curr].fi;
					}
					PP[B[X[it]]]={A[X[it]],X[it]};
					R=B[X[it]];
					st.erase(it);
					break;
				}
				if (mn==d[rit[R]][B[X[it]]]){
					int curr=B[X[it]];
					while (curr!=R){
						PP[curr]={pp[rit[R]][curr].fi,pp[rit[R]][curr].se};
						curr=pp[rit[R]][curr].fi;
					}
					PP[A[X[it]]]={B[X[it]],X[it]};
					R=A[X[it]];
					st.erase(it);
					break;
				}
			}
			
			if (rit[R]==-1) add(R);
		}
		
		RR[x]=R;
		//cout<<"debug: "<<x<<" "<<R<<endl;
	}
	
	//rep(x,0,n) cout<<x<<" "<<PP[x].fi<<" "<<PP[x].se<<endl;
	
	rep(x,0,q){
		int grp=0;
		if (x){
			rep(i,0,4) if (s[k*5+(x-1)*4+i]=='1') grp+=1<<i;
		}
		
		grp=LL[grp];
		
		int curr=T[x];
		while (curr!=RR[grp]){
			PP[curr]={pp[rit[RR[grp]]][curr].fi,pp[rit[RR[grp]]][curr].se};
			curr=pp[rit[RR[grp]]][curr].fi;
		}
		
		vector<signed> stk;
		curr=T[x];
		while (curr){
			stk.pub(PP[curr].se);
			curr=PP[curr].fi;
		}
		
		reverse(all(stk));
		
		//for (auto it:stk) cout<<it<<" "; cout<<endl;
		answer(stk);
	}
}

• Subtask 1: 94 / 100