Submission #1266233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266233		thelegendary08	Spy 3 (JOI24_spy3)	C++17	42 / 100	261 ms	95412 KiB

Aoi

#include "Aoi.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<endl
#define dout(a) cout<<a<<' '<<#a<<endl
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
using namespace std;
struct edge{
	int to, w, dex; 
};
namespace {

signed variable_example = 0;

signed function_example(signed a, signed b) { return a + b; }
const signed mxn = 10005; 

vvi dist(mxn), from(mxn); 
vb autism(mxn * 2);
vector<vector<edge>>adj(mxn); 
const int lg = 9;
const int NL = 500; 
void gen_dist(int v){
	priority_queue<pair<int,int>>q; 
	dist[v].resize(mxn); from[v].resize(mxn); 
	f0r(i, mxn)dist[v][i] = 4e18; 
	q.push(mp(0,v)); dist[v][v]= 0; from[v][v] = -1; 
	while(!q.empty()){
		int node = q.top().second; q.pop(); 
		for(auto u : adj[node]){
			int b = u.to; int w = u.w; 
			if(dist[v][b] > dist[v][node] + w){
				from[v][b] = u.dex; 
				dist[v][b] = dist[v][node] + w; 
				q.push(mp(-dist[v][b], b));
			}
		}
	}
	
}

string conv(int x){
	// dout(x);
	string ret = "";
	f0r(i, lg){
		if((1<<i) & x)ret += '1';
		else ret += '0'; 
	}
	return ret; 
}
}  // 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) {
  	f0r(i, M){
  		adj[A[i]].pb({B[i], C[i], i});
  		adj[B[i]].pb({A[i], C[i], i});
  	}
  	sort(all(X)); 
  	// dout("SDFHSDF");
  	mii cmp; int cnt = 0; 
  	for(auto u : X){
  		autism[u] = 1; 
  		cmp[u] = cnt; cnt++; 
  	}
  	gen_dist(0); 
  	// f0r(i, N)cout<<dist[0][i]<<' '; cout<<'\n';
  	vb vau(M); 
  	string ans = ""; 
  	
  	for(auto x : T){
  		int cur = x;
  		vi au; 
  		while(cur != 0){
  			int ed = from[0][cur];
  			if(A[ed] == cur){
  				cur = B[ed]; 
  			}
  			else cur = A[ed]; 
  			if(autism[ed]){
  				au.pb(cmp[ed]);
  				if(vau[ed])break; 
  				vau[ed] = 1; 
  			}
  		}
  		for(auto u : au){
  			ans += conv(u); 
  		}
  		ans += conv(NL);
  	}
  	// out(ans); 
  	return ans; 
}

Bitaro

#include "Bitaro.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<endl
#define dout(a) cout<<a<<' '<<#a<<endl
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
using namespace std;
struct edge{
	int to, w, dex; 
};
struct DSU{
	int n; vi par, sz; 
	DSU(int x){
		n=x; par.resize(n); sz.resize(n);
		f0r(i,n)par[i] = i, sz[i] = 1; 
	}
	int get(int x){
		while(x != par[x])x = par[x]; 
		return x; 
	}
	void unite(int a, int b){
		a = get(a); b = get(b); 
		if(a == b)return; 
		if(sz[a] < sz[b])swap(a,b); sz[a] += sz[b]; par[b] = a; 
	}
};
namespace {
const signed mxn = 10005; 
vvi dist(mxn), from(mxn); 
vb autism(mxn * 2);
vector<vector<edge>>adj(mxn); 
vi par(mxn,-1); 
const int lg = 9;
const int NL = 500; 
void gen_dist(int v, int t1, int t2){
	priority_queue<pair<int,int>>q; 
	dist[v].resize(mxn); from[v].resize(mxn); 
	f0r(i, mxn)dist[v][i] = 4e18, from[v][i] = -1; 
	q.push(mp(0,v)); dist[v][v]= 0; from[v][v] = -1; 
	while(!q.empty()){
		int node = q.top().second; q.pop(); 
		if(node == t1 || node == t2){
			// dout(node); 
			return;
		}
		 
		// dout2(node, dist[v][node]);
		for(auto u : adj[node]){
			int b = u.to; int w = u.w; 
			if(w >= 0 && dist[v][b] > dist[v][node] + w){
				from[v][b] = u.dex; 
				dist[v][b] = dist[v][node] + w; 
				q.push(mp(-dist[v][b], b));
			}
		}
	}
	
}
}  // 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) {
            	
    // DSU D = DSU(N); 
    f0r(i, M){
  		adj[A[i]].pb({B[i], C[i], i});
  		adj[B[i]].pb({A[i], C[i], i});
  		if(C[i] != -1){
  			// D.unite(A[i], B[i]);
  		}
  	}
  	
  	sort(all(X)); 
  	mii cmp; int cnt = 0; 
  	for(auto u : X){
  		autism[u] = 1; 
  		cmp[u] = cnt; cnt++; 
  	}
    vvi tra(T.size()); 
    int pt = 0; 
    for(int i = 0; i < s.size(); i += lg){
    	int cur = 0; 
    	for(int j = i; j < i + lg; j++){
    		cur += (1<<(j - i)) * (s[j] - '0');
    	}
    	if(cur == NL)pt++; 
    	else tra[pt].pb(cur); 
    }
    
    gen_dist(0, -1,-1); 
    f0r(i, N)par[i] = from[0][i]; 
    int ptr = 0; 
    // f0r(i, N)cout<<from[0][i]<<' '; cout<<'\n';
    for(auto vau : tra){
    	vector<signed>ans; 
    	int cur = T[ptr]; 
    	// vout(vau); 
    	for(auto ed : vau){
    		int save = cur;  
    		ed = X[ed]; 
    		
    		// if(dist[cur].size() == 0){
	    		gen_dist(cur, A[ed], B[ed]); 
	    	// }
	    
	    	int a, b; 
	    	/*
	    	if(D.get(cur) == D.get(A[ed])){
	    		a = A[ed]; b = B[ed];
	    	}
	    	else b = A[ed]; a = B[ed]; 
	    	*/
	    	
    		if(dist[cur][A[ed]] < dist[cur][B[ed]]){
    			a = A[ed]; b = B[ed]; 
    		}
    		else{
    			b = A[ed]; a = B[ed]; 
    		}
    		
    		// dout2(a,b); 
    		// if(dist[a].size() == 0){
    			gen_dist(a, cur, cur); 
    		// }
    		while(cur != a){
    			ans.pb(from[a][cur]); 
    			par[cur] = from[a][cur]; 
    			if(A[from[a][cur]] == cur){
    				cur = B[from[a][cur]];
    			}
    			else cur = A[from[a][cur]];
    		}
    		par[a] = ed; 
    		ans.pb(ed); 
    		cur = b; 
    	}
    	int save = 0; 
    	while(cur != 0){
    		ans.pb(par[cur]); 
			if(A[par[cur]] == cur){
				cur = B[par[cur]];
			}
			else cur = A[par[cur]];
    	}
    	// vout(ans); 
    	reverse(all(ans)); 
    	// vout(ans); 
    	answer(ans); 
    	ptr++; 
    	
    	
    }
    
    // while(true){
//     	
    // }
    
    
}

• Subtask 1: 42 / 100