Submission #1039446

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1039446	2024-07-30T22:02:08 Z	Trent	Spy 3 (JOI24_spy3)	C++17	0 / 100	21 ms	6408 KB

Aoi

#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;
	}
}

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);
	vector<bool> vis(N);
	vector<int> pre(N);
	priority_queue<node> dij;
	dij.push({0, 0});
	dis[0] = 0, vis[0] = true;
	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;
}

Bitaro

#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;
	}
}

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);
		vector<bool> vis(N);
		vector<int> pre(N);
		priority_queue<node> dij;
		dij.push({0, 0});
		dis[0] = 0, vis[0] = true;
		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	Incorrect	21 ms	6408 KB	Wrong Answer [5]
2	Halted	0 ms	0 KB	-