oj.uz

Submission #1039450

# Submission time Handle Problem Language Result Execution time Memory
1039450 2024-07-30T22:12:58 Z Trent Spy 3 (JOI24_spy3) C++17
0 / 100
 1000 ms 8076 KB 
#include "Aoi.h"
#include "bits/stdc++.h"

using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()

namespace {
	typedef long long ll;
	struct pii{int a, b;};
	bool operator <(pii a, pii b) {return a.a < b.a || a.a == b.a && a.b < b.b;}
	struct edge{int t; ll len;};
	struct node{int i; ll to;};
	bool operator <(node a, node b){
		return a.to > b.to;
	}
	const ll INF = 1e17;
}

std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
                std::vector<int> B, std::vector<long long> C,
                std::vector<int> T, std::vector<int> X) {
	string ret;
	vector<vector<edge>> adj(N);
	map<pii, int> xi;
	forR(i, M){
		adj[A[i]].push_back({B[i], C[i]});
		adj[B[i]].push_back({A[i], C[i]});
	}
	forR(i, K){
		xi.insert({{A[X[i]], B[X[i]]}, i});
		xi.insert({{B[X[i]], A[X[i]]}, i});
	}

	// dijkstra
	vector<ll> dis(N, INF);
	vector<bool> vis(N);
	vector<int> pre(N);
	priority_queue<node> dij;
	dij.push({0, 0});
	dis[0] = 0;
	while(!dij.empty()){
		auto [cur, len] = dij.top();
		dij.pop();
		if(!vis[cur]){
			vis[cur] = true;
			for(auto [to, el] : adj[cur]){
				if(len + el < dis[to]){
					dis[to] = len + el;
					pre[to] = cur;
					dij.push({to, dis[to]});
				}
			}
		}
	}

	forR(i, Q){
		vector<int> pth;
		for(int j = T[i]; j != 0; j = pre[j]) pth.push_back(j);
		pth.push_back(0);
		reverse(all(pth));
		string app = "";
		forR(j, K) app.push_back('0');
		forR(j, (int) pth.size() - 1){
			if(xi.count({pth[j], pth[j+1]})) {
				app[xi[{pth[j],pth[j+1]}]] = '1';
			}
		}
		ret += app;
	}
	cerr << ret << '\n';
	return ret;
}

#include "Bitaro.h"
#include "bits/stdc++.h"

using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()

namespace {
	typedef long long ll;
	struct pii{int a, b;};
	bool operator <(pii a, pii b) {return a.a < b.a || a.a == b.a && a.b < b.b;}
	struct edge{int t, ind; ll len;};
	struct node{int i; ll to;};
	bool operator <(node a, node b){
		return a.to > b.to;
	}
	const ll INF = 1e17;
}

void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B,
            std::vector<long long> C, std::vector<int> T, std::vector<int> X,
            std::string s) {
	map<pii, int> xi;
	forR(i, K){
		xi.insert({{A[X[i]], B[X[i]]}, i});
		xi.insert({{B[X[i]], A[X[i]]}, i});
	}

	vector<vector<edge>> adj(N);
	map<pii, int> ei;
	forR(i, M){
		int cxi = -1;
		if(xi.count({A[i], B[i]})){
			cxi = xi[{A[i], B[i]}];
		}
		adj[A[i]].push_back({B[i], cxi, C[i]});
		adj[B[i]].push_back({A[i], cxi, C[i]});
		ei[{A[i], B[i]}] = i;
		ei[{B[i], A[i]}] = i;
	}

	forR(i, Q){
		string curInfo = s.substr(K * i, K);
		vector<ll> dis(N, INF);
		vector<bool> vis(N);
		vector<int> pre(N);
		priority_queue<node> dij;
		dij.push({0, 0});
		dis[0] = 0;
		while(!dij.empty()){
			auto [cur, len] = dij.top();
			dij.pop();
			if(!vis[cur]){
				for(auto [to, ind, el] : adj[cur]){
					if(ind == -1 || curInfo[ind] == '1'){
						el = ind == -1 ? el : 0;
						if(len + el < dis[to]){
							dis[to] = len + el;
							pre[to] = cur;
							dij.push({to, dis[to]});
						}
					}
				}	
			}
		}
		vector<int> pth;
		for(int j = T[i]; j != 0; j = pre[j]) pth.push_back(j);
		pth.push_back(0);
		reverse(all(pth));
		for(int j : pth) cerr << j << ' ';
		cerr << '\n';
		vector<int> ret;
		forR(j, (int) pth.size() - 1) ret.push_back(ei[{pth[j], pth[j+1]}]);
		answer(ret);
	}
}

Compilation message

Aoi.cpp: In function 'bool {anonymous}::operator<({anonymous}::pii, {anonymous}::pii)':
Aoi.cpp:12:64: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   12 |  bool operator <(pii a, pii b) {return a.a < b.a || a.a == b.a && a.b < b.b;}
      |                                                     ~~~~~~~~~~~^~~~~~~~~~~~

Bitaro.cpp: In function 'bool {anonymous}::operator<({anonymous}::pii, {anonymous}::pii)':
Bitaro.cpp:12:64: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   12 |  bool operator <(pii a, pii b) {return a.a < b.a || a.a == b.a && a.b < b.b;}
      |                                                     ~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 26 ms 6160 KB Partially correct
2 Correct 1 ms 776 KB Output is correct
3 Partially correct 47 ms 6928 KB Partially correct
4 Partially correct 165 ms 6932 KB Partially correct
5 Partially correct 44 ms 6968 KB Partially correct
6 Partially correct 69 ms 6844 KB Partially correct
7 Partially correct 41 ms 6844 KB Partially correct
8 Partially correct 63 ms 6848 KB Partially correct
9 Partially correct 151 ms 6840 KB Partially correct
10 Correct 36 ms 6728 KB Output is correct
11 Partially correct 41 ms 7084 KB Partially correct
12 Correct 77 ms 7112 KB Output is correct
13 Partially correct 46 ms 6840 KB Partially correct
14 Partially correct 41 ms 6968 KB Partially correct
15 Correct 120 ms 6832 KB Output is correct
16 Correct 32 ms 6372 KB Output is correct
17 Partially correct 254 ms 7000 KB Partially correct
18 Partially correct 278 ms 7084 KB Partially correct
19 Partially correct 49 ms 7972 KB Partially correct
20 Partially correct 42 ms 8076 KB Partially correct
21 Partially correct 45 ms 8012 KB Partially correct
22 Execution timed out 1105 ms 7964 KB Time limit exceeded
23 Halted 0 ms 0 KB -