Submission #1280953

#TimeUsernameProblemLanguageResultExecution timeMemory
1280953trideserSpy 3 (JOI24_spy3)C++20
0 / 100
124 ms10280 KiB
#include "Aoi.h" #include <bits/stdc++.h> using namespace std; #define ll long long namespace { int variable_example = 0; int function_example(int a, int b) { return a + b; } } // namespace 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<int> parent(N, -1); vector<ll> eee(N); vector<long long> dist(N, -1); priority_queue<tuple<ll, ll, ll, ll>> q; q.push(make_tuple(0, 0, -1, -1)); vector<vector<tuple<ll, ll, ll>>> edges(N); for(int i = 0; i < M; i++) { ll a = A[i]; ll b = B[i]; ll c = C[i]; edges[a].push_back(make_tuple(b, c, i)); edges[b].push_back(make_tuple(a, c, i)); } while(!q.empty()) { ll d, node, p, eg; tie(d, node, p, eg) = q.top(); d *= -1; q.pop(); if(dist[node] != -1) continue; dist[node] = d; parent[node] = p; eee[node] = eg; for(tuple<ll, ll, ll> e : edges[node]) { q.push(make_tuple(-(d + get<1>(e)), get<0>(e), node, get<2>(e))); } } map<int, int> mp; for(int i = 0; i < K; i++) { mp[X[i]] = i; } string s(9 * K + 9 * Q, '1'); for(int i = 0; i < N; i++) { if(mp.find(eee[i]) == mp.end()) continue; ll current = parent[i]; while(current != -1) { if(mp.find(eee[current]) != mp.end()) { for(int j = 0; j < 9; j++) { int r = mp[eee[i]]; s[9 * r + j] = (char) ((eee[current] >> j) & 1) + 48; } break; } current = parent[current]; } } for(int i = 0; i < Q; i++) { ll current = T[i]; while(current != -1) { if(mp.find(eee[current]) != mp.end()) { for(int j = 0; j < 9; j++) { s[9 * K + 9 * i + j] = (char) ((eee[current] >> j) & 1) + 48; } break; } current = parent[current]; } } // cout << s << "\n"; return s; }
#include "Bitaro.h" #include <bits/stdc++.h> using namespace std; #define ll long long namespace { int variable_example = 0; int function_example(int a, int b) { return a + b; } } // namespace 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) { vector<ll> tree_parent(K); for(int i = 0; i < K; i++) { int a = 0; for(int j = 0; j < 9; j++) { a += (s[9 * i + j] - 48) << j; } if(a == 511) a = -1; tree_parent[i] = a; } cout << "\n"; for(int a : tree_parent) cout << a << " "; cout << " <-tree\n"; for (int i = 0; i < Q; i++) { vector<ll> newC = C; int a = 0; for(int j = 0; j < 9; j++) { a += ((int) s[9 * (i + K) + j] - 48) << j; } if(a == 511) a = -1; //cout << "\n" << a << "\n"; for(int j = 0; j < K; j++) { newC[X[j]] = 0x7fffffffffff; } while(a != -1) { newC[X[a]] = 0; a = tree_parent[a]; } for(ll a : newC) cout << a << " "; cout << "\n"; vector<int> parent(N, -1); vector<ll> eee(N); vector<long long> dist(N, -1); priority_queue<tuple<ll, ll, ll, ll>> q; q.push(make_tuple(0, 0, -1, -1)); vector<vector<tuple<ll, ll, ll>>> edges(N); for(int i = 0; i < M; i++) { ll a = A[i]; ll b = B[i]; ll c = newC[i]; edges[a].push_back(make_tuple(b, c, i)); edges[b].push_back(make_tuple(a, c, i)); } while(!q.empty()) { ll d, node, p, eg; tie(d, node, p, eg) = q.top(); d *= -1; q.pop(); if(dist[node] != -1) continue; dist[node] = d; parent[node] = p; eee[node] = eg; for(tuple<ll, ll, ll> e : edges[node]) { q.push(make_tuple(-(d + get<1>(e)), get<0>(e), node, get<2>(e))); } } vector<int> v; int node = T[i]; while(node != -1) { if(eee[node] != -1) v.push_back(eee[node]); node = parent[node]; } reverse(v.begin(), v.end()); answer(v); } }
#Verdict Execution timeMemoryGrader output
Fetching results...