oj.uz

답안 #1038109

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1038109 2024-07-29T12:58:56 Z AmirAli_H1 Spy 3 (JOI24_spy3) C++17
0 / 100
 60 ms 6548 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<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 + k, 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++) s += to_binary(res[i], 5);
	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; 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 = 0;
		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++) {
		int j = get_num(lx, lx + 5);
		lsw[j].pb(e); lx += 5;
	}
	
	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
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 19 ms 5036 KB Partially correct
2 Correct 1 ms 2316 KB Output is correct
3 Partially correct 35 ms 5504 KB Partially correct
4 Partially correct 36 ms 5824 KB Partially correct
5 Partially correct 46 ms 5624 KB Partially correct
6 Partially correct 42 ms 5500 KB Partially correct
7 Partially correct 39 ms 5508 KB Partially correct
8 Partially correct 31 ms 5788 KB Partially correct
9 Partially correct 24 ms 5648 KB Partially correct
10 Correct 19 ms 5356 KB Output is correct
11 Partially correct 42 ms 5640 KB Partially correct
12 Correct 39 ms 5540 KB Output is correct
13 Correct 46 ms 5580 KB Output is correct
14 Correct 43 ms 5492 KB Output is correct
15 Correct 33 ms 5540 KB Output is correct
16 Correct 17 ms 5288 KB Output is correct
17 Partially correct 45 ms 6548 KB Partially correct
18 Partially correct 52 ms 6548 KB Partially correct
19 Partially correct 53 ms 6052 KB Partially correct
20 Partially correct 38 ms 6052 KB Partially correct
21 Partially correct 54 ms 6292 KB Partially correct
22 Partially correct 55 ms 6156 KB Partially correct
23 Partially correct 40 ms 6312 KB Partially correct
24 Partially correct 60 ms 6056 KB Partially correct
25 Incorrect 36 ms 5384 KB Unexpected end of file - int32 expected
26 Halted 0 ms 0 KB -