Submission #1038128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038128		AmirAli_H1	Spy 3 (JOI24_spy3)	C++17	100 / 100	61 ms	6592 KiB

Aoi

// In the name of Allah

#include <bits/stdc++.h>
#include "Aoi.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);

namespace {

const int maxn = 2e4 + 4;
const ll oo = 1e18 + 4;

int n, m, q, k;
vector<int> adj[maxn];
vector<int> adjx[maxn];
vector<pair<pii, ll>> E;
int ind[maxn], M[maxn];
int res[maxn]; string s;
ll dis[maxn]; int mark[maxn], par[maxn];
priority_queue<pll> qu;
vector<int> ls, ls1, ls2;

void dij(int v) {
	fill(dis, dis + n, oo);
	fill(mark, mark + n, 0); fill(par, par + n, -1);
	dis[v] = 0; qu.push(Mp(-dis[v], v));
	while (!qu.empty()) {
		int v = qu.top().S; qu.pop();
		if (mark[v]) continue;
		mark[v] = 1;
		for (int j : adj[v]) {
			int u = E[j].F.F; ll w = E[j].S;
			if (u == v) u = E[j].F.S;
			if (dis[v] + w < dis[u]) {
				dis[u] = dis[v] + w;
				par[u] = j; qu.push(Mp(-dis[u], u));
			}
		}
	}
}

string to_binary(int x, int r) {
	string res = "";
	for (int j = r - 1; j >= 0; j--) {
		if (x & (1 << j)) res += "1";
		else res += "0";
	}
	return res;
}

void dfs(int v) {
	if (ind[v] != -1) ls.pb(ind[v]);
	for (int u : adjx[v]) {
		dfs(u);
	}
}

}

string aoi(int Nx, int Mx, int Qx, int Kx, vector<int> Ax,
                vector<int> Bx, vector<ll> Cx,
                vector<int> Tx, vector<int> Rx) {
    n = Nx; m = Mx; q = Qx; k = Kx;
    
	fill(ind, ind + n, -1);
	for (int i = 0; i < q; i++) {
		int v = Tx[i]; ind[v] = i;
	}
	
	fill(M, M + m, -1);
	for (int i = 0; i < k; i++) {
		int j = Rx[i]; M[j] = i;
	}
	for (int i = 0; i < m; i++) {
    	int u = Ax[i], v = Bx[i]; ll w = Cx[i];
    	adj[u].pb(i); adj[v].pb(i);
    	E.pb(Mp(Mp(u, v), w));
	}
	
	dij(0);
	for (int v = 0; v < n; v++) {
		int j = par[v];
		if (j != -1) {
			int u = E[j].F.F;
			if (u == v) u = E[j].F.S;
			adjx[u].pb(v);
		}
	}
	dfs(0);
	for (int i = 0; i < q; i++) {
		s += to_binary(ls[i], 4);
	}
	
	ls1.clear(); ls2.clear();
	fill(res, res + maxn, q);
	for (int i = 0; i < q; i++) {
		int v = Tx[ls[i]];
		while (v != 0) {
			int j = par[v];
			if (M[j] != -1) ls2.pb(M[j]);
			if (E[j].F.F != v) v = E[j].F.F;
			else v = E[j].F.S;
		}
		reverse(all(ls2));
		
		int R = 0;
		while (R < min(len(ls1), len(ls2))) {
			if (ls1[R] == ls2[R]) R++;
			else break;
		}
		for (int e = R; e < len(ls2); e++) res[ls2[e]] = i;
		
		s += to_binary(len(ls1) - R, 9);
		ls1.clear(); swap(ls1, ls2);
	}
	
	for (int i = 0; i < k; i += 3) s += to_binary(res[i] + (res[i + 1] * 17) + (res[i + 2] * 289), 13);
	return s;
}

Bitaro

// In the name of Allah

#include <bits/stdc++.h>
#include "Aoi.h"
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);

namespace {

const int maxn = 2e4 + 4;
const int maxq = 20;
const ll oo = 1e18 + 4;

int n, m, q, k; string s;
vector<int> adj[maxn];
vector<pair<pii, ll>> E;
int ind[maxn], M[maxn];
ll dis[maxn]; int mark[maxn], par[maxn];
priority_queue<pll> qu;
vector<int> ans[maxq];
vector<int> ls, lsx, lsw[maxq];
vector<int> Rx; int ok[maxn];

void dij(int v) {
	fill(dis, dis + n, oo);
	fill(mark, mark + n, 0); fill(par, par + n, -1);
	dis[v] = 0; qu.push(Mp(-dis[v], v));
	while (!qu.empty()) {
		int v = qu.top().S; qu.pop();
		if (mark[v]) continue;
		mark[v] = 1;
		for (int j : adj[v]) {
			int u = E[j].F.F; ll w = E[j].S;
			if (u == v) u = E[j].F.S;
			if (dis[v] + w < dis[u]) {
				dis[u] = dis[v] + w;
				par[u] = j; qu.push(Mp(-dis[u], u));
			}
		}
	}
}

void check_ans(int i, vector<int> Tx) {
	for (int e = 0; e < k; e++) {
		if (ok[e]) {
			int j = Rx[e];
			int u = E[j].F.F, v = E[j].F.S;
			adj[u].pb(j); adj[v].pb(j);
		}
	}
	
	dij(0); int v = Tx[i];
	while (v != 0) {
		int j = par[v];
		ans[i].pb(j);
		if (E[j].F.F != v) v = E[j].F.F;
		else v = E[j].F.S;
	}
	reverse(all(ans[i]));
	
	for (int e = 0; e < k; e++) {
		if (ok[e]) {
			int j = Rx[e];
			int u = E[j].F.F, v = E[j].F.S;
			adj[u].pop_back(); adj[v].pop_back();
		}
	}
}

bool cmp(int i, int j) {
	int j1 = Rx[i], j2 = Rx[j];
	return min(dis[E[j1].F.F], dis[E[j1].F.S]) < min(dis[E[j2].F.F], dis[E[j2].F.S]);
}

int get_num(int l, int r) {
	int res = 0, j = 0;
	for (int i = r - 1; i >= l; i--) {
		if (s[i] == '1') res += (1 << j);
		j++;
	}
	return res;
}

}

void answer(const vector<int> &e);

void bitaro(int Nx, int Mx, int Qx, int Kx, vector<int> Ax,
                vector<int> Bx, vector<ll> Cx,
                vector<int> Tx, vector<int> Rw, string sx) {
    n = Nx; m = Mx; q = Qx; k = Kx; s = sx; Rx = Rw;
    
	fill(ind, ind + n, -1);
	for (int i = 0; i < q; i++) {
		int v = Tx[i]; ind[v] = i;
	}
	
	fill(M, M + m, -1);
	for (int i = 0; i < k; i++) {
		int j = Rx[i]; M[j] = i;
	}
	for (int i = 0; i < m; i++) {
    	int u = Ax[i], v = Bx[i]; ll w = Cx[i];
    	if (M[i] == -1) {
			adj[u].pb(i); adj[v].pb(i);
		}
		else w = 1;
		E.pb(Mp(Mp(u, v), w));
	}
	
	int sz = 0;
	for (int i = 0; i < q; i++) {
		ls.pb(get_num(sz, sz + 4)); sz += 4;
	}
	
	int lx = q * 13;
	for (int e = 0; e < k; e += 3) {
		int j = get_num(lx, lx + 13); lx += 13;
		lsw[j % 17].pb(e); lsw[(j / 17) % 17].pb(e + 1);
		lsw[(j / 289) % 17].pb(e + 2);
	}
	
	lsx.clear();
	for (int i = 0; i < q; i++) {
		int R = get_num(sz, sz + 9); sz += 9;
		while (R--) lsx.pop_back();
		for (int e : lsw[i]) lsx.pb(e);
		
		fill(ok, ok + k, 0);
		for (int e : lsx) ok[e] = 1;
		check_ans(ls[i], Tx);
		sort(all(lsx), cmp);
	}
	
	for (int i = 0; i < q; i++) answer(ans[i]);
	return ;
}

• Subtask 1: 100 / 100