Submission #1039463

# Submission time Handle Problem Language Result Execution time Memory
1039463 2024-07-30T23:33:30 Z Trent Spy 3 (JOI24_spy3) C++17
0 / 100
26 ms 6376 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;
	string toBinNumber(int x, int bits) {
		string ret;
		forR(i, bits) {
			ret.push_back(x % 2 == 0 ? '0' : '1');
			x /= 2;
		}
		reverse(all(ret));
		assert(x == 0);
		return ret;
	}
}
 
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) {
	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});
	}
 
	vector<int> indIn(K, Q);
	vector<int> lOld(Q);
	// dijkstra
	forR(i, Q){
		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]});
					}
				}
			}
		}
 
		vector<int> pth;
		for(int j = T[i]; j != 0; j = pre[j]) pth.push_back(j);
		pth.push_back(0);
		reverse(all(pth));
		int lasUsed = -1;
		forR(j, (int) pth.size() - 1) {
			if(xi.count({pth[j], pth[j+1]})) {
				int eInd = xi[{pth[j], pth[j+1]}];
				if(indIn[eInd] == Q) {
					indIn[eInd] = i;
				} else {
					lasUsed = eInd;
				}
			}
		}
		lOld[i] = lasUsed == -1 ? -1 : lasUsed;
	}
 
  set<int> sUsedX;
  for(int i : lOld) if(i != -1) sUsedX.insert(i);
  vector<int> usedX;
  for(int i : sUsedX) usedX.push_back(i);

	for(int i : indIn) cerr << i << ' ';
	cerr << '\n';
	for(int i : lOld) cerr << i << ' ';
	cerr << '\n';
  for(int i : usedX) cerr << i << ' ';
  cerr << '\n';

	string ret;
	for(int i : indIn) {
    if(!sUsedX.count(i)) ret += toBinNumber(i, 5);
    else {
      assert(i + 1 < Q);
      ret += toBinNumber(i + Q + 1, 5);
    }
	}
	for(int i : lOld) {
    if(i == -1) ret += toBinNumber(usedX.size(), 4);
    else {
      forR(j, usedX.size()) if(usedX[j] == i) ret += toBinNumber(j, 4);
    }
	}
	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;
	int fromBinNumber(string s) {
		int ret = 0;
		for(char i : s) ret = ret * 2 + (i == '0' ? 0 : 1);
		return ret;
	}
}
 
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;
	}
 
	vector<int> indIn;
	vector<int> lOld;
  vector<int> usedX;
	int ci=0;
	forR(i, K) {
    int val = fromBinNumber(s.substr(ci, 5));
    if(val >= Q + 1) {
      usedX.push_back(i);
      indIn.push_back(val - Q - 1);
    } else {
      indIn.push_back(val);
    }
		ci += 5;
	}
	forR(i, Q) {
    int val = fromBinNumber(s.substr(ci, 4));
    if(val == usedX.size()) lOld.push_back(-1);
    else lOld.push_back(usedX[val]);
		ci += 4;
	}

	for(int i : indIn) cerr << i << ' ';
	cerr << '\n';
	for(int i : lOld) cerr << i << ' ';
	cerr << '\n';
 
	vector<bool> solid(N, false);
	vector<int> sPre(N);
	forR(i, Q){
		vector<ll> dis(N, INF);
		vector<bool> vis(N);
		vector<int> pre(N);
		int stNode;
		if(lOld[i] == -1) stNode = 0;
		else {
			int eInd = X[lOld[i]];
			stNode = sPre[A[eInd]] == B[eInd] ? A[eInd] : B[eInd];
			assert(solid[stNode]);
		}
 
		priority_queue<node> dij;
		dij.push({stNode, 0});
		dis[stNode] = 0;
		while(!dij.empty()){
			auto [cur, len] = dij.top();
			dij.pop();
			if(!vis[cur]){
				vis[cur] = true;
				for(auto [to, ind, el] : adj[cur]){
					if(ind == -1 || indIn[ind] == i){
						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 != stNode; j = pre[j]) pth.push_back(j);
		for(int j = stNode; j != 0; j = sPre[j]) pth.push_back(j);
		pth.push_back(0);
		reverse(all(pth));
		for(int j : pth) cerr << j << ' ';
		cerr << '\n';
		REP(j, 1, pth.size()) {
			solid[pth[j]] = true;
			sPre[pth[j]] = pth[j-1];
		}
		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;}
      |                                                     ~~~~~~~~~~~^~~~~~~~~~~~
Aoi.cpp: In function 'std::string aoi(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<int>, std::vector<int>)':
Aoi.cpp:5:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define forR(i, x) for(int i = 0; i < (x); ++i)
      |                                     ^
Aoi.cpp:111:7: note: in expansion of macro 'forR'
  111 |       forR(j, usedX.size()) if(usedX[j] == i) ret += toBinNumber(j, 4);
      |       ^~~~

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;}
      |                                                     ~~~~~~~~~~~^~~~~~~~~~~~
Bitaro.cpp: In function 'void bitaro(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<long long int>, std::vector<int>, std::vector<int>, std::string)':
Bitaro.cpp:64:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     if(val == usedX.size()) lOld.push_back(-1);
      |        ~~~~^~~~~~~~~~~~~~~
Bitaro.cpp:6:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define REP(i, a, b) for(int i = (a); i < (b); ++i)
      |                                         ^
Bitaro.cpp:115:3: note: in expansion of macro 'REP'
  115 |   REP(j, 1, pth.size()) {
      |   ^~~
# Verdict Execution time Memory Grader output
1 Correct 26 ms 6376 KB Output is correct
2 Runtime error 1 ms 600 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -