Submission #1161821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161821		irmuun	Spy 3 (JOI24_spy3)	C++20	8 / 100	18 ms	3612 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 lg=40;

}  // 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="";
	for(int i:X){
		ll len=C[i];
		cerr<<len<<' ';
		for(int j=0;j<lg;j++){
			if(len&(1ll<<j)){
				s+='1';
			}
			else{
				s+='0';
			}
		}
	}
	// cerr<<endl;
	// cerr<<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 lg=40,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,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=0;i<N;i++){
	// 	cerr<<dist[i]<<' ';
	// }
	// cerr<<endl;
	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;
  	for(int i=0;i<K;i++){
  		ll len=0;
  		for(int j=0;j<lg;j++){
  			if(s[i*lg+j]=='1') len+=(1ll<<j);
  		}
  		C[X[i]]=len;
  		// cerr<<len<<endl;
  	}
  	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});
  	}
  	dijkstra();
  	for(int u:T){
  		vector<int>path;
  		int cur=u;
  		while(cur!=0){
  			path.pb(edge[cur]);
  			cur=from[cur];
  		}
  		reverse(all(path));
  		answer(path);
  	}
  	return;
}

• Subtask 1: 8 / 100