| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1002292 |
2024-06-19T11:56:46 Z |
c2zi6 |
Train (APIO24_train) |
C++17 |
|
42 ms |
19860 KB |
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "train.h"
typedef tuple<int, int, int, int> PIII;
void ktrel(VI& a) {
int n = a.size();
sort(all(a));
VI b;
b.pb(a[0]);
replr(i, 1, n-1) if (a[i] != a[i-1]) {
b.pb(a[i]);
}
a = b;
}
namespace TEST2 {
int n, m;
ll solve(int N, int M, int W, VI T, VI X, VI Y, VI A, VI B, VI C, VI L, VI R) {
n = N;
m = M;
VVI timeframes(n);
/* compress */ {
rep(i, m) {
int& u = X[i];
int& v = Y[i];
int& l = A[i];
int& r = B[i];
timeframes[u].pb(l);
timeframes[v].pb(r);
}
rep(u, n) ktrel(timeframes[u]);
rep(i, m) {
int& u = X[i];
int& v = Y[i];
int& l = A[i];
int& r = B[i];
l = lower_bound(all(timeframes[u]), l) - timeframes[u].begin();
r = lower_bound(all(timeframes[v]), r) - timeframes[v].begin();
}
}
VPI state; /*node, time */
rep(u, n) {
rep(i, timeframes[u].size()) {
state.pb({u, i});
}
}
/*rep(u, state.size()) {*/
/* cout << "STATE " << u << ": ";*/
/* cout << state[u].ff << " " << state[u].ss << endl;*/
/*}*/
VVPI gp(state.size());
VI nodeidx(n);
rep(i, state.size()-1) {
if (state[i].ff == state[i+1].ff) {
/*cout << i << " " << i+1 << " " << 0 << endl;*/
gp[i].pb({i+1, 0});
} else {
nodeidx[state[i+1].ff] = i+1;
}
}
auto getstate = [&](int node, int time) {
return nodeidx[node] + time;
};
rep(i, m) {
int& u = X[i];
int& v = Y[i];
int& l = A[i];
int& r = B[i];
int& w = C[i];
int from = getstate(u, l);
int to = getstate(v, r);
/*cout << from << " " << to << " " << w << endl;*/
gp[from].pb({to, w});
}
VL dist(state.size(), 1e18);
VI vis(state.size());
priority_queue<PLL> pq;
pq.push({0, 0});
dist[0] = 0;
while (pq.size()) {
int u = pq.top().ss;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto[v, w] : gp[u]) {
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({-dist[v], v});
}
}
}
return dist.back();
}
};
ll solve(int N, int M, int W, VI T, VI X, VI Y, VI A, VI B, VI C, VI L, VI R) {
if (W == 0) return TEST2::solve(N, M, W, T, X, Y, A, B, C, L, R);
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
19860 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
19860 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Wrong Answer. |
| 2 |
Halted |
0 ms |
0 KB |
- |
