Submission #71233

#	Time	Username	Problem	Language	Result	Execution time	Memory
71233		zscoder	한자 끝말잇기 (JOI14_kanji)	C++17	100 / 100	325 ms	52544 KiB

Anna

#include "Annalib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const ll INF = ll(4e18);

ll cost[333][333];
vi adj[333];
int n;
int par[333];
ll dist[333];

ll D[333][333];
ll D1[333][333];

void floyd()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			D[i][j]=0;
			if(i!=j) D[i][j]=cost[i][j];
		}
	}
	for(int k=0;k<n;k++)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				D[i][j]=min(D[i][k]+D[k][j], D[i][j]);
			}
		}
	}
}

void floyd1()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			D1[i][j]=0;
			if(i!=j) D1[i][j]=cost[i][j];
		}
	}
	for(int k=0;k<n;k++)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				D1[i][j]=min(D1[i][k]+D1[k][j], D1[i][j]);
			}
		}
	}
}
int SS[55555];
int TT[55555];
int AA[55555];
int UU[55555];
int BB[55555];

pair<vi,vi> prepcomp(int i, int j, vi V, int K)
{
	//cerr<<"PRECOMP : "<<i<<' '<<j<<'\n';
	//for(int v:V) cerr<<v<<' ';
	//cerr<<'\n';
	vi L,R;
	int u1=AA[UU[i]]; int v1=BB[UU[i]];
	if(j==K)
	{
		vector<pair<ll,ll> > vec;
		for(int k:V)
		{
			int s=SS[k]; int t=TT[k];
			ll cost = D1[s][t]-D1[s][u1]-D1[v1][t];
			if(D1[s][t]>=INF) cost=INF;
			//cerr<<"COST A : "<<cost<<' '<<k<<'\n';
			vec.pb(mp(cost,k));
		}
		sort(vec.begin(),vec.end());
		int c=V.size(); int pt=0;
		for(;pt<vec.size();pt++)
		{
			int k=vec[pt].se;
			//cerr<<vec[pt].fi<<' '<<k<<' '<<cost[u1][v1]<<'\n';
			if(vec[pt].fi>cost[u1][v1])
			{
				//first point which works
				if(c==V.size()) c=pt;
				L.pb(k);
			}
			else
			{
				R.pb(k);
			}
		}
		//cerr<<"CA : "<<i<<' '<<j<<' '<<c<<'\n';
		int mx=int(V.size())+1;
		int cnt=0;
		while(mx>(1<<cnt)) cnt++;
		for(int k=0;k<cnt;k++)
		{
			if(c&(1<<k)) Tap(1);
			else Tap(0);
		}
	}
	else
	{
		int u2=AA[UU[j]]; int v2=BB[UU[j]];
		vector<pair<ll,ll> > vec;
		for(int k:V)
		{
			int s=SS[k]; int t=TT[k];
			ll cost = D1[v2][t]-D1[v1][t];
			//cerr<<cost<<' '<<k<<'\n';
			vec.pb(mp(cost,k));
		}
		sort(vec.begin(),vec.end());
		int c=V.size(); int pt=0;
		for(;pt<vec.size();pt++)
		{
			int k=vec[pt].se;
			//cerr<<pt<<' '<<u1<<' '<<v1<<' '<<u2<<' '<<v2<<'\n';
			if(vec[pt].fi>cost[u1][v1]-cost[u2][v2])
			{
				//first point which works
				if(c==V.size()) c=pt; 
				L.pb(k);
			}
			else
			{
				R.pb(k);
			}
		}
		int mx=int(V.size())+1;
		int cnt=0;
		while(mx>(1<<cnt)) cnt++;
		for(int k=0;k<cnt;k++)
		{
			if(c&(1<<k)) Tap(1);
			else Tap(0);
		}
	}
	//cerr<<"END PRECOMP "<<i<<' '<<j<<'\n';
	return mp(L,R);
}

vector<vi> solve(int l, int r, int K, int Q)
{
	vi vec;
	for(int i=0;i<Q;i++) vec.pb(i);
	if(l>r) return {};
	if(l==r) return {vec};
	//cerr<<"SOLVE "<<l<<' '<<r<<'\n';
	int mid=(l+r)>>1;
	vector<vi> L = solve(l,mid,K,Q);
	vector<vi> R = solve(mid+1,r,K,Q);
	vector<ii> lab(Q,mp(-1,-1));
	for(int i=0;i<L.size();i++)
	{
		for(int v:L[i])
		{
			lab[v].fi=l+i;
		}
	}
	for(int i=0;i<R.size();i++)
	{
		for(int v:R[i])
		{
			lab[v].se=mid+1+i;
		}
	}
	for(int i=0;i<Q;i++){assert(lab[i].fi>=0&&lab[i].se>=0);}
	vector<int> exist[11][11];
	for(int i=0;i<Q;i++)
	{
		exist[lab[i].fi][lab[i].se].pb(i);
	}
	vector<vi> ans(r-l+1);
	for(int i=l;i<=mid;i++)
	{
		for(int j=mid+1;j<=r;j++)
		{
			int tmp = exist[i][j].size();
			if(tmp>0)
			{
				pair<vi,vi> pairv = prepcomp(i, j, exist[i][j], K);
				for(int x:pairv.fi) ans[i-l].pb(x);
				for(int x:pairv.se) ans[j-l].pb(x);
			}
		}
	}
	return ans;
}

void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) 
{
	n=N;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cost[i][j]=INF;
		}
	}
	for(int i=0;i<Q;i++)
	{
		SS[i]=S[i]; TT[i]=T[i];
	}
	for(int i=0;i<M;i++)
	{
		AA[i]=A[i]; BB[i]=B[i];
		adj[A[i]].pb(B[i]);
		cost[A[i]][B[i]] = C[i];
	}
	//vi best;	
	floyd();
	vector<ll> tempor(K,INF);
	for(int i=0;i<K;i++)
	{
		UU[i]=U[i];
		swap(tempor[i], cost[A[U[i]]][B[U[i]]]);
	}
	floyd1();
	for(int i=0;i<K;i++)
	{
		swap(tempor[i], cost[A[U[i]]][B[U[i]]]);
	}
	/*
	for(int j=0;j<Q;j++)
	{
		best.pb(K);
		//dijkstra(S[j]);
		int u=A[U[0]]; 
		ll cur=D[S[j]][u]; ll bestd=D[S[j]][T[j]];
		for(int i=0;i<K;i++)
		{
			int v=B[U[i]]; //dijkstra(v);
			if(cur+cost[u][v]+D[v][T[j]]==bestd)
			{
				best[int(best.size())-1]=i; break;
			}
		}
	}
	const int MX = 60;
	while(int(best.size())<MX) best.pb(0);
	for(int i=0;i<MX;i+=3)
	{
		int b2 = best[i+2]; int b1 = best[i+1]; int b0 = best[i];
		int comb = b2*36+b1*6+b0;
		for(int j=0;j<8;j++)
		{
			Tap((comb&(1<<j))?1:0);
		}
	}
	*/
	vector<vi> res = solve(0,K,K,Q);
	/*
	vi best(Q);
	for(int i=0;i<=K;i++)
	{
		for(int v:res[i]) 
		{
			best[v]=i;
		}
	}
	for(int i=0;i<Q;i++)
	{
		cerr<<"BEST A "<<i<<' '<<best[i]<<'\n';
	}
	*/
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const ll INF = ll(4e18);

ll cost2[333][333];
vector<ii> adj2[333];
int nn;
ii par2[333];
ll dist2[333];
ll D2[333][333];

void dijkstra2(int s)
{
	//cerr<<"DIJK "<<s<<'\n';
	for(int i=0;i<nn;i++)
	{
		dist2[i]=INF; par2[i]=mp(-1,-1);
	}
	priority_queue<ii,vector<ii>,greater<ii> > pq;
	dist2[s]=0; pq.push(mp(0,s));
	while(!pq.empty())
	{
		ll d=pq.top().fi; int u=pq.top().se; pq.pop();
		for(ii X:adj2[u])
		{
			int v=X.fi; int lab=X.se;
			ll c = cost2[u][v];
			if(d+c<dist2[v])
			{
				//cerr<<"PAR "<<v<<" = "<<u<<'\n';
				par2[v]=mp(u,lab); dist2[v]=d+c; pq.push(mp(dist2[v],v));
			}
		}
	}
}

void floyd2()
{
	for(int i=0;i<nn;i++)
	{
		for(int j=0;j<nn;j++)
		{
			D2[i][j]=0;
			if(i!=j) D2[i][j]=cost2[i][j];
		}
	}
	for(int k=0;k<nn;k++)
	{
		for(int i=0;i<nn;i++)
		{
			for(int j=0;j<nn;j++)
			{
				D2[i][j]=min(D2[i][k]+D2[k][j], D2[i][j]);
			}
		}
	}
}

void getpath(int s, int u)
{
	vi path;
	//cerr<<"GET PATH "<<s<<' '<<u<<'\n';
	int cur = s; 
	while(cur!=u)
	{
		for(ii x:adj2[cur])
		{
			int v=x.fi; int lab=x.se;
			if(D2[s][cur]+cost2[cur][v]+D2[v][u]==D2[s][u])
			{
				Answer(lab); cur=v; break;
			}
		}
	}
}

int SSS[555];
int TTT[55555];
int AAA[55555];
int UUU[55555];
int BBB[55555];
int ZZ[55555];
int PTR;
pair<vi,vi> prepcomp2(int i, int j, vi V, int K)
{
	//cerr<<"PRECOMP 2 : "<<i<<' '<<j<<'\n';
	//for(int v:V) cerr<<v<<' ';
	//cerr<<'\n';
	vi L,R;
	int u1=AAA[UUU[i]]; int v1=BBB[UUU[i]];
	if(j==K)
	{
		vector<pair<ll,ll> > vec;
		for(int k:V)
		{
			int s=SSS[k]; int t=TTT[k];
			ll cost = D2[s][t]-D2[s][u1]-D2[v1][t];
			if(D2[s][t]>=INF) cost=INF;
			vec.pb(mp(cost,k));
			//cerr<<"COST B : "<<cost<<' '<<k<<'\n';
		}
		sort(vec.begin(),vec.end());
		int c=0;int pt=0;
		int mx=int(V.size())+1;
		int cnt=0;
		while(mx>(1<<cnt)) cnt++;
		for(int k=0;k<cnt;k++)
		{
			if(ZZ[PTR++]) c^=(1<<k);
		}
		for(;pt<vec.size();pt++)
		{
			int k=vec[pt].se;
			if(pt>=c)
			{
				L.pb(k);
			}
			else
			{
				R.pb(k);
			}
		}
		//cerr<<i<<' '<<j<<' '<<c<<'\n';
	}
	else
	{
		int u2=AAA[UUU[j]]; int v2=BBB[UUU[j]];
		vector<pair<ll,ll> > vec;
		for(int k:V)
		{
			int s=SSS[k]; int t=TTT[k];
			ll cost = D2[v2][t]-D2[v1][t];
			//cerr<<cost<<' '<<k<<'\n';
			vec.pb(mp(cost,k));
		}
		sort(vec.begin(),vec.end());
		int c=0;int pt=0;
		int mx=int(V.size())+1;
		int cnt=0;
		while(mx>(1<<cnt)) cnt++;
		for(int k=0;k<cnt;k++)
		{
			if(ZZ[PTR++]) c^=(1<<k);
		}
		for(;pt<vec.size();pt++)
		{
			int k=vec[pt].se;
			if(pt>=c)
			{
				L.pb(k);
			}
			else
			{
				R.pb(k);
			}
		}
		//cerr<<i<<' '<<j<<' '<<c<<'\n';
	}
	return mp(L,R);
}


vector<vi> solve2(int l, int r, int K, int Q)
{
	vi vec;
	for(int i=0;i<Q;i++) vec.pb(i);
	if(l>r) return {};
	if(l==r) return {vec};
	int mid=(l+r)>>1;
	vector<vi> L = solve2(l,mid,K,Q);
	vector<vi> R = solve2(mid+1,r,K,Q);
	vector<ii> lab(Q,mp(-1,-1));
	for(int i=0;i<L.size();i++)
	{
		for(int v:L[i])
		{
			lab[v].fi=l+i;
		}
	}
	for(int i=0;i<R.size();i++)
	{
		for(int v:R[i])
		{
			lab[v].se=mid+1+i;
		}
	}
	for(int i=0;i<Q;i++){assert(lab[i].fi>=0&&lab[i].se>=0);}
	vector<int> exist[11][11];
	for(int i=0;i<Q;i++)
	{
		exist[lab[i].fi][lab[i].se].pb(i);
	}
	vector<vi> ans(r-l+1);
	for(int i=l;i<=mid;i++)
	{
		for(int j=mid+1;j<=r;j++)
		{
			int tmp = exist[i][j].size();
			//cerr<<i<<' '<<j<<' '<<tmp<<'\n';
			if(tmp>0)
			{
				pair<vi,vi> pairv = prepcomp2(i, j, exist[i][j], K);
				for(int x:pairv.fi) ans[i-l].pb(x);
				for(int x:pairv.se) ans[j-l].pb(x);
			}
		}
	}
	return ans;
}

//int dp[111][10][10]; 

void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) 
{
	for(int i=0;i<L;i++) ZZ[i]=X[i];
	PTR=0;
	nn=N;
	for(int i=0;i<nn;i++)
	{
		for(int j=0;j<nn;j++)
		{
			cost2[i][j]=INF;
		}
	}
	for(int i=0;i<Q;i++)
	{
		SSS[i]=S[i]; TTT[i]=T[i];
	}
	for(int i=0;i<M;i++)
	{
		AAA[i]=A[i]; BBB[i]=B[i];
		adj2[A[i]].pb(mp(B[i],i));
		if(C[i]!=-1) cost2[A[i]][B[i]] = C[i];
	}
	for(int i=0;i<K;i++)
	{
		UUU[i]=U[i];
	}
	vector<int> best(Q);
	/*
	for(int i=0;i<L;i+=8)
	{
		int cur=i; int as=0;
		for(int j=0;j<8;j++)
		{
			if(X[cur]) as+=(1<<j);
			cur++;
		}
		best.pb(as%6);
		as/=6;
		best.pb(as%6);
		as/=6;
		best.pb(as%6);
	}
	*/
	int ptr=0;
	floyd2();
	/*
	for(int i=0;i<=K;i++)
	{
		int u1=A[U[i]]; int v1=B[U[i]];
		for(int j=i+1;j<=K;j++)
		{
			if(j==K)
			{
				vector<pair<ll,ll> > vec;
				for(int k=0;k<Q;k++)
				{
					int s=S[k]; int t=T[k];
					ll cost = D2[s][t]-D2[s][u1]-D2[v1][t];
					if(D2[s][t]>=INF) cost=INF;
					vec.pb(mp(cost,k));
				}
				sort(vec.begin(),vec.end());
				int c=0;
				for(int k=0;k<6;k++)
				{
					if(X[ptr++]) c^=(1<<k);
				}
				for(int k=0;k<Q;k++)
				{
					if(k>=c)
					{
						dp[vec[k].se][i][j]=1; //i better
					}
					else
					{
						dp[vec[k].se][i][j]=0; //j better
					}
				}
			}
			else
			{
				int u2=A[U[j]]; int v2=B[U[j]];
				vector<pair<ll,ll> > vec;
				for(int k=0;k<Q;k++)
				{
					int s=S[k]; int t=T[k];
					ll cost = D2[v2][t]-D2[v1][t];
					vec.pb(mp(cost,k));
				}
				sort(vec.begin(),vec.end());
				int c=0;
				for(int k=0;k<6;k++)
				{
					if(X[ptr++]) c^=(1<<k);
				}
				for(int k=0;k<Q;k++)
				{
					if(k>=c)
					{
						dp[vec[k].se][i][j]=1; //i better
					}
					else
					{
						dp[vec[k].se][i][j]=0; //j better
					}
				}
			}
		}
	}
	for(int i=0;i<Q;i++) //find best for each i
	{
		int cur=0;
		for(int j=0;j<=K;j++)
		{
			if(j!=cur) continue;
			for(int k=j+1;k<=K;k++)
			{
				if(!dp[i][j][k])
				{
					cur=k; break;
				}
			}
		}
		best[i]=cur;
	}
	*/
	vector<vi> res = solve2(0,K,K,Q);
	for(int i=0;i<=K;i++)
	{
		for(int v:res[i]) 
		{
			best[v]=i;
		}
	}
	/*
	for(int i=0;i<Q;i++)
	{
		cerr<<"BEST B "<<i<<' '<<best[i]<<'\n';
	}
	*/
	for(int i=0;i<Q;i++)
	{
		int s=S[i]; int e=T[i];
		if(best[i]==K)
		{
			getpath(s,e);
			Answer(-1);
		}
		else
		{
			int u = A[U[best[i]]]; int v = B[U[best[i]]];
			//cerr<<s<<' '<<e<<' '<<"U V : "<<U[best[i]]<<' '<<u<<' '<<v<<'\n';
			getpath(s,u);
			Answer(U[best[i]]);
			getpath(v,e);
			Answer(-1);
		}
	}
}

Compilation message (stderr)

Anna.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > prepcomp(int, int, vi, int)':
Anna.cpp:100:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;pt<vec.size();pt++)
        ~~^~~~~~~~~~~
Anna.cpp:107:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(c==V.size()) c=pt;
        ~^~~~~~~~~~
Anna.cpp:131:8: warning: unused variable 's' [-Wunused-variable]
    int s=SS[k]; int t=TT[k];
        ^
Anna.cpp:138:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;pt<vec.size();pt++)
        ~~^~~~~~~~~~~
Anna.cpp:145:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(c==V.size()) c=pt; 
        ~^~~~~~~~~~
Anna.cpp: In function 'std::vector<std::vector<int> > solve(int, int, int, int)':
Anna.cpp:177:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<L.size();i++)
              ~^~~~~~~~~
Anna.cpp:184:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<R.size();i++)
              ~^~~~~~~~~

Bruno.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > prepcomp2(int, int, vi, int)':
Bruno.cpp:128:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;pt<vec.size();pt++)
        ~~^~~~~~~~~~~
Bruno.cpp:148:8: warning: unused variable 's' [-Wunused-variable]
    int s=SSS[k]; int t=TTT[k];
        ^
Bruno.cpp:162:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;pt<vec.size();pt++)
        ~~^~~~~~~~~~~
Bruno.cpp:144:7: warning: unused variable 'u2' [-Wunused-variable]
   int u2=AAA[UUU[j]]; int v2=BBB[UUU[j]];
       ^~
Bruno.cpp: In function 'std::vector<std::vector<int> > solve2(int, int, int, int)':
Bruno.cpp:190:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<L.size();i++)
              ~^~~~~~~~~
Bruno.cpp:197:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<R.size();i++)
              ~^~~~~~~~~
Bruno.cpp: In function 'void Bruno(int, int, int*, int*, long long int*, int, int*, int*, int, int*, int, int*)':
Bruno.cpp:273:6: warning: unused variable 'ptr' [-Wunused-variable]
  int ptr=0;
      ^~~

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 8 / 8
• Subtask 4: 40 / 40
• Subtask 5: 20 / 20