Submission #1162548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162548		irmuun	Spy 3 (JOI24_spy3)	C++20	0 / 100	8 ms	3032 KiB

Aoi

#include "Aoi.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

namespace {

const int maxn=1e4+5;

int from[maxn],edge[maxn];
long long dist[maxn];

vector<tuple<int,ll,int>>g[maxn];

}  // namespace

string aoi(int N, int M, int Q, int K, vector<int> A,vector<int> B, vector<long long> C,
			vector<int> T,vector<int> X) {
	string s="";
	fill(dist,dist+N,(ll)1e18);
	for(int i=0;i<M;i++){
		g[A[i]].pb({B[i],C[i],i});
		g[B[i]].pb({A[i],C[i],i});
	}
	set<pair<ll,int>>st;
	st.insert({0,0});
	dist[0]=0;
	while(!st.empty()){
		ll D=st.begin()->ff,i=st.begin()->ss;
		st.erase(st.begin());
		if(dist[i]!=D) continue;
		for(auto [j,w,e]:g[i]){
			if(dist[i]+w<dist[j]){
				edge[j]=e;
				from[j]=i;
				dist[j]=dist[i]+w;
				st.insert({dist[j],j});
			}
		}
	}
	for(int i=1;i<N;i++){
		for(int j=0;j<15;j++){
			if(edge[i]&(1<<j)){
				s+='1';
			}
			else{
				s+='0';
			}
		}
	}
	cout<<s<<endl;
	return s;
}

Bitaro

#include "Bitaro.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

namespace {

const int maxn=1e4+5;

int N,M;
int from[maxn],edge[maxn];
long long dist[maxn];

vector<tuple<int,ll,int>>g[maxn];

void dijkstra(){
	fill(dist,dist+N,(ll)1e18);
	set<pair<ll,int>>st;
	st.insert({0,0});
	dist[0]=0;
	while(!st.empty()){
		ll D=st.begin()->ff;
		int i=st.begin()->ss;
		st.erase(st.begin());
		if(dist[i]!=D) continue;
		for(auto [j,w,e]:g[i]){
			if(dist[i]+w<dist[j]){
				edge[j]=e;
				from[j]=i;
				dist[j]=dist[i]+w;
				st.insert({dist[j],j});
			}
		}
	}
	return;
}

}  // namespace

void bitaro(int N, int M, int Q, int K, vector<int> A, vector<int> B,
			vector<long long> C, vector<int> T, vector<int> X,string s) {
	::N=N;
	::M=M;
	int len=s.size();
	vector<pair<int,int>>adj[N];
	for(int i=0;i<len/15;i++){
		int ind=0;
		for(int j=0;j<15;j++){
			if(s[i*15+j]=='1'){
				ind+=(1<<j);
			}
		}
		adj[A[ind]].pb({B[ind],ind});
		adj[B[ind]].pb({A[ind],ind});
	}
	vector<bool>used(N,0);
	queue<int>q;
	q.push(0);
	used[0]=true;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(auto [y,e]:adj[x]){
			if(!used[y]){
				used[y]=true;
				from[y]=x;
				edge[y]=e;
				q.push(y);
			}
		}
	}
	for(int i=0;i<Q;i++){
		int cur=T[i];
		vector<int>path;
		while(cur>0){
			path.pb(edge[cur]);
			cur=from[cur];
		}
		answer(path);
	}
	return;
}

• Subtask 1: 0 / 100