Submission #1162498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162498		irmuun	Spy 3 (JOI24_spy3)	C++20	0 / 100	12 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});
			}
		}
	}
	vector<bool>used(M,false);
	for(int i=0;i<Q;i++){
		fill(all(used),false);
		int cur=T[i];
		while(cur>0){
			used[edge[cur]]=true;
			cur=from[cur];
		}
		for(int j=0;j<K;j++){
			if(used[X[j]]==true){
				s+='1';
			}
			else{
				s+='0';
			}
		}
	}
	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;
	for(int i=0;i<M;i++){
		if(C[i]==-1) continue;
		g[A[i]].pb({B[i],C[i],i});
		g[B[i]].pb({A[i],C[i],i});
	}
	for(int i=0;i<Q;i++){
		vector<bool>used(K,false);
		for(int j=0;j<K;j++){
			if(s[i*K+j]=='1'){
				used[j]=true;
			}
		}
		for(int j=0;j<K;j++){
			if(used[j]==true){
				g[A[X[j]]].pb({B[X[j]],1,X[j]});
				g[B[X[j]]].pb({A[X[j]],1,X[j]});
			}
		}
		dijkstra();
		vector<int>path;
		int cur=T[i];
		while(cur!=0){
			path.pb(edge[cur]);
			cur=from[cur];
		}
		answer(path);
		for(int j=0;j<K;j++){
			if(used[j]==true){
				g[A[X[j]]].pop_back();
				g[B[X[j]]].pop_back();
			}
		}
	}	
	return;
}

• Subtask 1: 0 / 100