# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
638570 |
2022-09-06T12:04:44 Z |
KYoA_A |
Robot (JOI21_ho_t4) |
C++17 |
|
393 ms |
43620 KB |
/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define dbg(x...)
#endif
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define rrep(a, b, c) for(int a = (b); a > c; --a)
#define each(a, b) for(auto& a : b)
#define sz(x) (int)(x).size()
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define vi vector<int>
#define ar array
template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define rsz resize
#define bk back()
#define pi pair<int, int>
#define pl pair<ll, ll>
#define mp make_pair
#define f first
#define s second
#define pct(x) __builtin_popcount(x)
constexpr int fsb(int x) {return __builtin_ffs(x) - 1;} // first set bit
constexpr int log2(int x) {return x == 0 ? 0 : 31-__builtin_clz(x);} // floor(log2(x))
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T> bool umin(T& a, const T& b){return b<a?a=b, 1:0;}
template <class T> bool umax(T& a, const T& b){return a<b?a=b, 1:0;}
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
using ll = long long;
using ld = long double;
using str = string;
const int inf = (int)1e9 + 5;
const ll infl = (ll)1e18 + 5;
const ld PI = acos((ld)-1);
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/
void solve(){
int n, m; cin >> n >> m;
V<ar<int, 4>> eg(m);
V<vi> g(n);
V<set<int>> vs(n), vs1(n);
rep(i, 0, m){
int u, v, c, z; cin >> u >> v >> c >> z;
--u; --v;
eg[i] = {u, v, c, z};
for(int x : {u, v}){
if(vs[x].count(c)){
vs1[x].emplace(c);
}else{
vs[x].emplace(c);
}
g[x].eb(i);
}
}
pqg <pl> pq;
V<ll> d(n, infl);
pq.emplace(d[0] = 0, 0);
while(!pq.empty()){
auto [cd, x] = pq.top(); pq.pop();
if(d[x] != cd) continue;
each(e, g[x]){
auto [u, v, c, z] = eg[e];
int y = x^u^v;
if(umin(d[y], d[x] + (vs1[x].count(c) ? z : 0))){
pq.emplace(d[y], y);
}
}
}
cout << (d.bk == infl ? -1 : d.bk) << '\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
13544 KB |
Output is correct |
2 |
Correct |
27 ms |
7124 KB |
Output is correct |
3 |
Correct |
104 ms |
13056 KB |
Output is correct |
4 |
Correct |
44 ms |
10180 KB |
Output is correct |
5 |
Incorrect |
393 ms |
43620 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |