Submission #1038006

# Submission time Handle Problem Language Result Execution time Memory
1038006 2024-07-29T12:04:53 Z AmirAli_H1 Spy 3 (JOI24_spy3) C++17
23 / 100
55 ms 5784 KB
// 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<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;

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 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 i = 0; i < q; i++) {
		int v = Tx[i];
		fill(res, res + k, 0);
		while (v != 0) {
			int j = par[v];
			if (M[j] != -1) res[M[j]] = 1;
			if (E[j].F.F != v) v = E[j].F.F;
			else v = E[j].F.S;
		}
		for (int i = 0; i < k; i++) {
			if (res[i]) s += "1";
			else s += "0";
		}
	}
	
	return s;
}
// 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;
vector<int> adj[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> ans[maxq];

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 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> Rx, string s) {
    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];
    	if (M[i] == -1) {
			adj[u].pb(i); adj[v].pb(i);
		}
		else w = 0;
		E.pb(Mp(Mp(u, v), w));
	}
	
	for (int i = 0; i < q; i++) {
		int l = i * k, r = (i + 1) * k;
		for (int e = l; e < r; e++) {
			if (s[e] == '1') {
				int j = Rx[e - l];
				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 = l; e < r; e++) {
			if (s[e] == '1') {
				int j = Rx[e - l];
				int u = E[j].F.F, v = E[j].F.S;
				adj[u].pop_back(); adj[v].pop_back();
			}
		}
	}
	
	for (int i = 0; i < q; i++) answer(ans[i]);
	return ;
}

Compilation message

Bitaro.cpp:35:5: warning: '{anonymous}::res' defined but not used [-Wunused-variable]
   35 | int res[maxn]; string s;
      |     ^~~
# Verdict Execution time Memory Grader output
1 Partially correct 13 ms 4636 KB Partially correct
2 Correct 1 ms 1812 KB Output is correct
3 Partially correct 31 ms 4776 KB Partially correct
4 Partially correct 26 ms 4796 KB Partially correct
5 Partially correct 38 ms 4620 KB Partially correct
6 Partially correct 34 ms 4784 KB Partially correct
7 Partially correct 34 ms 4532 KB Partially correct
8 Partially correct 30 ms 4772 KB Partially correct
9 Partially correct 26 ms 4652 KB Partially correct
10 Correct 15 ms 4644 KB Output is correct
11 Partially correct 34 ms 4628 KB Partially correct
12 Correct 36 ms 4784 KB Output is correct
13 Partially correct 38 ms 4796 KB Partially correct
14 Partially correct 31 ms 4736 KB Partially correct
15 Correct 31 ms 4776 KB Output is correct
16 Correct 14 ms 4620 KB Output is correct
17 Partially correct 44 ms 5292 KB Partially correct
18 Partially correct 41 ms 5516 KB Partially correct
19 Partially correct 44 ms 5616 KB Partially correct
20 Partially correct 38 ms 5784 KB Partially correct
21 Partially correct 41 ms 5668 KB Partially correct
22 Partially correct 53 ms 5776 KB Partially correct
23 Partially correct 38 ms 5640 KB Partially correct
24 Partially correct 55 ms 5644 KB Partially correct
25 Partially correct 43 ms 5316 KB Partially correct
26 Partially correct 42 ms 5308 KB Partially correct
27 Correct 1 ms 1804 KB Output is correct
28 Partially correct 34 ms 5100 KB Partially correct
29 Partially correct 18 ms 4616 KB Partially correct
30 Correct 38 ms 5116 KB Output is correct
31 Correct 25 ms 5036 KB Output is correct
32 Partially correct 42 ms 5384 KB Partially correct
33 Correct 40 ms 4936 KB Output is correct
34 Partially correct 42 ms 5224 KB Partially correct
35 Correct 30 ms 5288 KB Output is correct
36 Partially correct 30 ms 5292 KB Partially correct
37 Partially correct 10 ms 3608 KB Partially correct
38 Partially correct 20 ms 4664 KB Partially correct
39 Partially correct 19 ms 4492 KB Partially correct
40 Correct 8 ms 3996 KB Output is correct
41 Partially correct 48 ms 5088 KB Partially correct
42 Partially correct 32 ms 5588 KB Partially correct
43 Correct 52 ms 5592 KB Output is correct
44 Correct 17 ms 5636 KB Output is correct
45 Partially correct 11 ms 3472 KB Partially correct
46 Partially correct 13 ms 4256 KB Partially correct
47 Correct 14 ms 4192 KB Output is correct
48 Correct 0 ms 1812 KB Output is correct
49 Correct 1 ms 1804 KB Output is correct
50 Partially correct 11 ms 4628 KB Partially correct
51 Partially correct 2 ms 1820 KB Partially correct
52 Partially correct 1 ms 1804 KB Partially correct
53 Partially correct 15 ms 4540 KB Partially correct
54 Partially correct 10 ms 3600 KB Partially correct
55 Partially correct 28 ms 4016 KB Partially correct
56 Partially correct 24 ms 5228 KB Partially correct
57 Partially correct 41 ms 5076 KB Partially correct
58 Partially correct 38 ms 4600 KB Partially correct
59 Partially correct 46 ms 5544 KB Partially correct
60 Partially correct 38 ms 5380 KB Partially correct
61 Partially correct 51 ms 5620 KB Partially correct
62 Partially correct 46 ms 5028 KB Partially correct
63 Partially correct 47 ms 5640 KB Partially correct
64 Correct 14 ms 5184 KB Output is correct
65 Partially correct 23 ms 4660 KB Partially correct
66 Partially correct 23 ms 5620 KB Partially correct
67 Partially correct 28 ms 4680 KB Partially correct
68 Partially correct 25 ms 5672 KB Partially correct
69 Correct 2 ms 1804 KB Output is correct
70 Correct 1 ms 1804 KB Output is correct
71 Correct 1 ms 1804 KB Output is correct
72 Partially correct 11 ms 3512 KB Partially correct
73 Partially correct 24 ms 4116 KB Partially correct
74 Partially correct 24 ms 4132 KB Partially correct
75 Correct 10 ms 4116 KB Output is correct
76 Correct 1 ms 2056 KB Output is correct
77 Correct 32 ms 4760 KB Output is correct
78 Partially correct 27 ms 4776 KB Partially correct
79 Correct 33 ms 4748 KB Output is correct
80 Correct 1 ms 1804 KB Output is correct
81 Partially correct 38 ms 4620 KB Partially correct
82 Partially correct 39 ms 4724 KB Partially correct
83 Partially correct 44 ms 4740 KB Partially correct