QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #442177 | #8232. Yet Another Shortest Path Query | Rong7 | ML | 3261ms | 663252kb | C++14 | 7.2kb | 2024-06-15 09:47:48 | 2024-06-15 09:47:48 |
Judging History
answer
// Not afraid to dark.
#include <bits/stdc++.h>
using namespace std;
clock_t start_time, end_time;
#define GET_START start_time = clock ();
#define GET_END end_time = clock (); fprintf (stderr, "TIME COSSEMED : %0.3lf\n", 1.0 * (end_time - start_time) / CLOCKS_PER_SEC);
#define inline __inline__ __attribute__ ((always_inline))
namespace io {
int read_pos, read_dt; char read_char;
inline int read (int &p = read_pos){
p = 0, read_dt = 1; read_char = getchar ();
while (! isdigit (read_char)){
if (read_char == '-')
read_dt = - 1;
read_char = getchar ();
}
while (isdigit (read_char)){
p = (p << 1) + (p << 3) + read_char - 48;
read_char = getchar ();
}
return p = p * read_dt;
}
int write_sta[65], write_top;
inline void write (int x){
if (x < 0)
putchar ('-'), x = - x;
write_top = 0;
do
write_sta[write_top ++] = x % 10, x /= 10;
while (x);
while (write_top)
putchar (write_sta[-- write_top] + 48);
}
int llen;
inline int get_string (char c[], int &len = llen){
len = 0;
read_char = getchar ();
while (read_char == ' ' || read_char == '\n' || read_char == '\r')
read_char = getchar ();
while (read_char != ' ' && read_char != '\n' && read_char != '\r'){
c[++ len] = read_char;
read_char = getchar ();
}
return len;
}
}
const int N = 1e6, inf = 0x3f3f3f3f;
int n, m;
int firs[N + 5], nex[N * 2 + 5], to[N * 2 + 5], w[N * 2 + 5], tot = 1;
int deg[N + 5];
bool vis[N + 5];
vector < int > gL[N + 5], tL[N + 5], gR[N + 5], tR[N + 5];
inline void Add (int u, int v, int l){
++ deg[u], ++ deg[v];
++ tot;
nex[tot] = firs[u];
firs[u] = tot;
to[tot] = v;
w[tot] = l;
++ tot;
nex[tot] = firs[v];
firs[v] = tot;
to[tot] = u;
w[tot] = l;
}
inline void Add_L (int u, int v, int e){
gL[v].push_back (e ^ 1);
tL[u].push_back (e);
}
inline void Add_R (int u, int v, int e){
gR[v].push_back (e ^ 1);
tR[u].push_back (e);
}
int Q, Ans[N * 10 + 5];
pair < int , int > Query[N + 5];
unordered_map < int , vector < int > > QS[N + 5], QT[N + 5];
unordered_map < int , vector < int > > qS[N + 5], qT[N + 5];
unordered_map < int , int > TT;
signed main (){
GET_START
io::read (n), io::read (m);
for (int i = 1, u, v, l;i <= m;++ i){
io::read (u), io::read (v), io::read (l);
Add (u, v, l);
}
queue < int > Que;
for (int i = 1;i <= n;++ i)
if (deg[i] <= 5)
Que.push (i);
while (! Que.empty ()){
int u = Que.front ();
Que.pop ();
vis[u] = true;
for (int e = firs[u], v;e;e = nex[e]){
v = to[e];
-- deg[v];
if (! vis[v])
Add_L (v, u, e ^ 1), Add_R (u, v, e);
if (deg[v] == 5)
Que.push (v);
}
}
io::read (Q);
for (int i = 1, s, t;i <= Q;++ i){
io::read (s), io::read (t);
Query[i] = make_pair (s, t);
QS[s][t].push_back (i);// , qS[s][t].push_back (i);
QT[t][s].push_back (i);// , qT[t][s].push_back (i);
int ned = i;
for (int e : tR[s]){
int u = to[e];
ned += Q;
qS[u][t].push_back (ned);
qT[t][u].push_back (ned);
}
for (int e : gL[t]){
int v = to[e];
ned += Q;
qS[s][v].push_back (ned);
qT[v][s].push_back (ned);
}
}
for (int i = 1;i <= Q;++ i)
for (int j = 0;j < 10;++ j)
Ans[i + j * Q] = inf;
for (int i = 1;i <= n;++ i){
TT.clear ();
int j, u, v, x, y, z;
for (int ej : tL[i]){
j = to[ej], x = w[ej];
if (! TT.count (j) || TT[j] > x)
TT[j] = x;
for (auto eu : tR[j]){
u = to[eu], y = w[eu];
if (! TT.count (u) || TT[u] > x + y)
TT[u] = x + y;
}
}
for (auto ej : tR[i]){
j = to[ej], x = w[ej];
if (! TT.count (j) || TT[j] > x)
TT[j] = x;
for (auto eu : tR[j]){
u = to[eu], y = w[eu];
if (TT[u] == 0 || TT[u] > x + y)
TT[u] = x + y;
}
}
TT[i] = 0;
for (auto re : TT){
tie (j, x) = re;
for (int t : qS[i][j])
Ans[t] = min (Ans[t], x);
}
for (int ej : tL[i]){
j = to[ej], x = w[ej];
for (int eu : tR[j]){
u = to[eu], y = w[eu];
for (int ev : tR[u]){
v = to[ev], z = w[ev];
if (! TT.count (v) || TT[v] > x + y + z)
TT[v] = x + y + z;
}
}
}
TT[i] = 0;
for (auto re : TT){
tie (j, x) = re;
for (int t : QS[i][j])
Ans[t] = min (Ans[t], x);
}
TT.clear ();
for (int ej : gR[i]){
j = to[ej], x = w[ej];
if (! TT.count (j) || TT[j] > x)
TT[j] = x;
for (int eu : gL[j]){
u = to[eu], y = w[eu];
if (! TT.count (u) || TT[u] > x + y)
TT[u] = x + y;
}
}
for (int ej : gL[i]){
j = to[ej], x = w[ej];
if (! TT.count (j) || TT[j] > x)
TT[j] = x;
for (int eu : gL[j]){
u = to[eu], y = w[eu];
if (! TT.count (u) || TT[u] > x + y)
TT[u] = x + y;
}
}
TT[i] = 0;
for (auto re : TT){
tie (j, x) = re;
for (int t : qT[i][j])
Ans[t] = min (Ans[t], x);
}
for (int ej : gR[i]){
j = to[ej], x = w[ej];
for (int eu : gL[j]){
u = to[eu], y = w[eu];
for (int ev : gL[u]){
v = to[ev], z = w[ev];
if (! TT.count (v) || TT[v] > x + y + z)
TT[v] = x + y + z;
}
}
}
TT[i] = 0;
for (auto re : TT){
tie (j, x) = re;
for (int t : QT[i][j])
Ans[t] = min (Ans[t], x);
}
// qS[i].clear (), QS[i].clear (), qT[i].clear (), QT[i].clear ();
}
for (int i = 1, s, t;i <= Q;++ i){
tie (s, t) = Query[i];
int ned = i;
for (int e : tR[s]){
int l = w[e];
ned += Q;
Ans[i] = min (Ans[i], Ans[ned] + l);
}
for (int e : gL[t]){
int l = w[e];
ned += Q;
Ans[i] = min (Ans[i], Ans[ned] + l);
}
if (Ans[i] ^ inf)
io::write (Ans[i]), puts ("");
else
puts ("-1");
}
GET_END
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 59ms
memory: 318596kb
input:
6 9 1 2 4 2 3 6 3 6 5 6 5 3 5 4 2 4 1 3 3 4 9 1 3 100 5 3 1 5 1 3 1 6 3 4 3 5 2 5
output:
6 8 3 1 7
result:
ok 5 number(s): "6 8 3 1 7"
Test #2:
score: 0
Accepted
time: 48ms
memory: 319660kb
input:
6 4 1 2 1 2 3 1 3 4 1 4 5 1 3 1 4 1 5 1 6
output:
3 -1 -1
result:
ok 3 number(s): "3 -1 -1"
Test #3:
score: 0
Accepted
time: 2976ms
memory: 631140kb
input:
40005 79608 1 2 70031203 1 3 99924845 1 4 61645659 1 5 9324967 2 3 15761918 3 4 62534796 4 5 35260314 5 2 35948540 6 2 23727405 6 7 83302920 7 3 31010426 7 8 75060393 8 4 94275932 8 9 99663793 9 5 81701979 9 6 439297 10 6 46955645 10 11 89514237 11 7 21257310 11 12 53896253 12 8 67933315 12 13 26161...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #4:
score: 0
Accepted
time: 3261ms
memory: 656040kb
input:
35479 70156 1 2 53094201 1 3 95796673 1 4 35585979 1 5 55612594 2 3 60766083 3 4 64392832 4 5 32896460 5 2 91649893 6 2 6196154 6 7 4986564 7 3 91799790 7 8 10909791 8 4 30034265 8 9 95672010 9 4 67004237 9 10 77872672 10 5 68900058 10 6 42927604 11 6 71288663 11 12 51597962 12 7 79690815 12 13 9742...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #5:
score: 0
Accepted
time: 3239ms
memory: 663252kb
input:
35811 70820 1 2 40434193 1 3 13483892 1 4 32864259 1 5 47591755 1 6 65123023 1 7 81695948 1 8 1102880 1 9 47223939 1 10 52947058 1 11 31439481 2 3 94162364 3 4 20590842 4 5 24137043 5 6 74926235 6 7 9376267 7 8 97130364 8 9 75568799 9 10 5022411 10 11 59066963 11 2 96177033 12 2 17823959 12 13 83906...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 1000000 numbers
Test #6:
score: -100
Memory Limit Exceeded
input:
200000 599952 127401 69434 88680591 127401 39916 10673559 127401 52475 59546013 127401 77787 74018113 127401 11462 7023970 60723 37187 65141305 60723 115008 72307785 60723 71812 47362248 60723 143858 20042617 60723 153890 48502784 60723 172009 21754689 60723 23327 97998405 63817 58332 30056889 63817...
output:
-1 -1 -1 -1 4704530 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -203619955 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 61255756 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 36218127 -1 -1 -1 7417612 -1 -1 -1 -1 -1 ...