#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int cura,nodea,statea,adda;
vector<int> dista,da;
vector<pair<int,int> > va[2005];
set<pair<int,int> > sa;
void upda(int node)
{
sa.erase({dista[node],node});
dista[node]=cura;
for (auto p:va[node])
{
if (cura+p.second<dista[p.first])
{
sa.erase({dista[p.first],p.first});
dista[p.first]=cura+p.second;
sa.insert({dista[p.first],p.first});
}
}
if (sa.empty())
return;
nodea=sa.begin()->second;
for (int i=0;i<9;i++)
SendA(min(dista[nodea]-cura,511)&(1<<i));
}
void InitA(int n,int a,vector<int> u,vector<int> v,vector<int> c)
{
for (int i=0;i<a;i++)
{
va[u[i]].push_back({v[i],c[i]});
va[v[i]].push_back({u[i],c[i]});
}
for (int i=0;i<n;i++)
{
dista.push_back(1e9);
sa.insert({dista[i],i});
}
upda(0);
}
void ReceiveA(bool x)
{
da.push_back(x);
if (!statea && da.size()==9)
{
adda=0;
for (int i=0;i<9;i++)
adda|=(da[i]<<i);
da.clear();
if (dista[nodea]<cura+adda)
{
cura=dista[nodea];
for (int i=0;i<11;i++)
SendA(nodea&(1<<i));
upda(nodea);
}
else
{
cura+=adda;
statea=1;
}
}
if (statea && da.size()==11)
{
int node=0;
for (int i=0;i<11;i++)
node|=(da[i]<<i);
da.clear();
statea=0;
upda(node);
}
}
vector<int> Answer()
{
return dista;
}
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
int curb,nodeb,stateb,addb;
vector<int> distb,db;
vector<pair<int,int> > vb[2005];
set<pair<int,int> > sb;
void updb(int node)
{
sb.erase({distb[node],node});
distb[node]=curb;
for (auto p:vb[node])
{
if (curb+p.second<distb[p.first])
{
sb.erase({distb[p.first],p.first});
distb[p.first]=curb+p.second;
sb.insert({distb[p.first],p.first});
}
}
if (sb.empty())
return;
nodeb=sb.begin()->second;
for (int i=0;i<9;i++)
SendB(min(distb[nodeb]-curb,511)&(1<<i));
}
void InitB(int n,int b,vector<int> u,vector<int> v,vector<int> c)
{
for (int i=0;i<b;i++)
{
vb[u[i]].push_back({v[i],c[i]});
vb[v[i]].push_back({u[i],c[i]});
}
for (int i=0;i<n;i++)
{
distb.push_back(1e9);
sb.insert({distb[i],i});
}
updb(0);
}
void ReceiveB(bool x)
{
db.push_back(x);
if (!stateb && db.size()==9)
{
addb=0;
for (int i=0;i<9;i++)
addb|=(db[i]<<i);
db.clear();
if (distb[nodeb]<=curb+addb)
{
curb=distb[nodeb];
for (int i=0;i<11;i++)
SendB(nodeb&(1<<i));
updb(nodeb);
}
else
{
curb+=addb;
stateb=1;
}
}
if (stateb && db.size()==11)
{
int node=0;
for (int i=0;i<11;i++)
node|=(db[i]<<i);
db.clear();
stateb=0;
updb(node);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1124 ms |
1824 KB |
Output is correct |
2 |
Correct |
7 ms |
1504 KB |
Output is correct |
3 |
Correct |
1436 ms |
1760 KB |
Output is correct |
4 |
Correct |
1182 ms |
20400 KB |
Output is correct |
5 |
Correct |
53 ms |
1640 KB |
Output is correct |
6 |
Correct |
1156 ms |
4800 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
1088 KB |
Output is correct |
2 |
Correct |
1188 ms |
2016 KB |
Output is correct |
3 |
Correct |
1128 ms |
2016 KB |
Output is correct |
4 |
Correct |
1644 ms |
55456 KB |
Output is correct |
5 |
Correct |
1556 ms |
48216 KB |
Output is correct |
6 |
Correct |
374 ms |
1320 KB |
Output is correct |
7 |
Correct |
1442 ms |
48560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1284 ms |
2016 KB |
Output is correct |
2 |
Correct |
6 ms |
1160 KB |
Output is correct |
3 |
Correct |
892 ms |
1760 KB |
Output is correct |
4 |
Correct |
1248 ms |
2032 KB |
Output is correct |
5 |
Correct |
955 ms |
2120 KB |
Output is correct |
6 |
Correct |
1434 ms |
1840 KB |
Output is correct |
7 |
Correct |
986 ms |
1712 KB |
Output is correct |
8 |
Correct |
1096 ms |
1712 KB |
Output is correct |
9 |
Correct |
1350 ms |
1856 KB |
Output is correct |
10 |
Correct |
1392 ms |
1872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
508 ms |
1536 KB |
Output is correct |
2 |
Correct |
421 ms |
1512 KB |
Output is correct |
3 |
Correct |
732 ms |
23696 KB |
Output is correct |
4 |
Correct |
326 ms |
1784 KB |
Output is correct |
5 |
Correct |
708 ms |
17320 KB |
Output is correct |
6 |
Correct |
492 ms |
1680 KB |
Output is correct |
7 |
Correct |
406 ms |
1568 KB |
Output is correct |
8 |
Correct |
852 ms |
1440 KB |
Output is correct |
9 |
Correct |
1000 ms |
36136 KB |
Output is correct |
10 |
Correct |
996 ms |
35912 KB |
Output is correct |
11 |
Correct |
1169 ms |
61088 KB |
Output is correct |
12 |
Correct |
908 ms |
53448 KB |
Output is correct |
13 |
Correct |
655 ms |
1856 KB |
Output is correct |
14 |
Correct |
6 ms |
1288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
508 ms |
1536 KB |
Output is correct |
2 |
Correct |
421 ms |
1512 KB |
Output is correct |
3 |
Correct |
732 ms |
23696 KB |
Output is correct |
4 |
Correct |
326 ms |
1784 KB |
Output is correct |
5 |
Correct |
708 ms |
17320 KB |
Output is correct |
6 |
Correct |
492 ms |
1680 KB |
Output is correct |
7 |
Correct |
406 ms |
1568 KB |
Output is correct |
8 |
Correct |
852 ms |
1440 KB |
Output is correct |
9 |
Correct |
1000 ms |
36136 KB |
Output is correct |
10 |
Correct |
996 ms |
35912 KB |
Output is correct |
11 |
Correct |
1169 ms |
61088 KB |
Output is correct |
12 |
Correct |
908 ms |
53448 KB |
Output is correct |
13 |
Correct |
655 ms |
1856 KB |
Output is correct |
14 |
Correct |
6 ms |
1288 KB |
Output is correct |
15 |
Correct |
652 ms |
1824 KB |
Output is correct |
16 |
Correct |
675 ms |
1816 KB |
Output is correct |
17 |
Correct |
588 ms |
1720 KB |
Output is correct |
18 |
Correct |
676 ms |
17584 KB |
Output is correct |
19 |
Correct |
642 ms |
1712 KB |
Output is correct |
20 |
Correct |
608 ms |
18064 KB |
Output is correct |
21 |
Correct |
794 ms |
2112 KB |
Output is correct |
22 |
Correct |
374 ms |
1744 KB |
Output is correct |
23 |
Correct |
1116 ms |
43968 KB |
Output is correct |
24 |
Correct |
1030 ms |
43776 KB |
Output is correct |
25 |
Correct |
1511 ms |
75208 KB |
Output is correct |
26 |
Correct |
1072 ms |
64520 KB |
Output is correct |
27 |
Correct |
640 ms |
2016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
508 ms |
1536 KB |
Output is correct |
2 |
Correct |
421 ms |
1512 KB |
Output is correct |
3 |
Correct |
732 ms |
23696 KB |
Output is correct |
4 |
Correct |
326 ms |
1784 KB |
Output is correct |
5 |
Correct |
708 ms |
17320 KB |
Output is correct |
6 |
Correct |
492 ms |
1680 KB |
Output is correct |
7 |
Correct |
406 ms |
1568 KB |
Output is correct |
8 |
Correct |
852 ms |
1440 KB |
Output is correct |
9 |
Correct |
1000 ms |
36136 KB |
Output is correct |
10 |
Correct |
996 ms |
35912 KB |
Output is correct |
11 |
Correct |
1169 ms |
61088 KB |
Output is correct |
12 |
Correct |
908 ms |
53448 KB |
Output is correct |
13 |
Correct |
655 ms |
1856 KB |
Output is correct |
14 |
Correct |
6 ms |
1288 KB |
Output is correct |
15 |
Correct |
652 ms |
1824 KB |
Output is correct |
16 |
Correct |
675 ms |
1816 KB |
Output is correct |
17 |
Correct |
588 ms |
1720 KB |
Output is correct |
18 |
Correct |
676 ms |
17584 KB |
Output is correct |
19 |
Correct |
642 ms |
1712 KB |
Output is correct |
20 |
Correct |
608 ms |
18064 KB |
Output is correct |
21 |
Correct |
794 ms |
2112 KB |
Output is correct |
22 |
Correct |
374 ms |
1744 KB |
Output is correct |
23 |
Correct |
1116 ms |
43968 KB |
Output is correct |
24 |
Correct |
1030 ms |
43776 KB |
Output is correct |
25 |
Correct |
1511 ms |
75208 KB |
Output is correct |
26 |
Correct |
1072 ms |
64520 KB |
Output is correct |
27 |
Correct |
640 ms |
2016 KB |
Output is correct |
28 |
Correct |
634 ms |
1960 KB |
Output is correct |
29 |
Correct |
654 ms |
1760 KB |
Output is correct |
30 |
Correct |
1106 ms |
42016 KB |
Output is correct |
31 |
Correct |
744 ms |
1760 KB |
Output is correct |
32 |
Correct |
1194 ms |
37216 KB |
Output is correct |
33 |
Correct |
900 ms |
1568 KB |
Output is correct |
34 |
Correct |
806 ms |
2000 KB |
Output is correct |
35 |
Correct |
582 ms |
1592 KB |
Output is correct |
36 |
Correct |
1432 ms |
49328 KB |
Output is correct |
37 |
Correct |
1380 ms |
49232 KB |
Output is correct |
38 |
Correct |
1658 ms |
85344 KB |
Output is correct |
39 |
Correct |
1354 ms |
78472 KB |
Output is correct |
40 |
Correct |
974 ms |
2272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1124 ms |
1824 KB |
Output is correct |
2 |
Correct |
7 ms |
1504 KB |
Output is correct |
3 |
Correct |
1436 ms |
1760 KB |
Output is correct |
4 |
Correct |
1182 ms |
20400 KB |
Output is correct |
5 |
Correct |
53 ms |
1640 KB |
Output is correct |
6 |
Correct |
1156 ms |
4800 KB |
Output is correct |
7 |
Correct |
4 ms |
1088 KB |
Output is correct |
8 |
Correct |
1188 ms |
2016 KB |
Output is correct |
9 |
Correct |
1128 ms |
2016 KB |
Output is correct |
10 |
Correct |
1644 ms |
55456 KB |
Output is correct |
11 |
Correct |
1556 ms |
48216 KB |
Output is correct |
12 |
Correct |
374 ms |
1320 KB |
Output is correct |
13 |
Correct |
1442 ms |
48560 KB |
Output is correct |
14 |
Correct |
1284 ms |
2016 KB |
Output is correct |
15 |
Correct |
6 ms |
1160 KB |
Output is correct |
16 |
Correct |
892 ms |
1760 KB |
Output is correct |
17 |
Correct |
1248 ms |
2032 KB |
Output is correct |
18 |
Correct |
955 ms |
2120 KB |
Output is correct |
19 |
Correct |
1434 ms |
1840 KB |
Output is correct |
20 |
Correct |
986 ms |
1712 KB |
Output is correct |
21 |
Correct |
1096 ms |
1712 KB |
Output is correct |
22 |
Correct |
1350 ms |
1856 KB |
Output is correct |
23 |
Correct |
1392 ms |
1872 KB |
Output is correct |
24 |
Correct |
508 ms |
1536 KB |
Output is correct |
25 |
Correct |
421 ms |
1512 KB |
Output is correct |
26 |
Correct |
732 ms |
23696 KB |
Output is correct |
27 |
Correct |
326 ms |
1784 KB |
Output is correct |
28 |
Correct |
708 ms |
17320 KB |
Output is correct |
29 |
Correct |
492 ms |
1680 KB |
Output is correct |
30 |
Correct |
406 ms |
1568 KB |
Output is correct |
31 |
Correct |
852 ms |
1440 KB |
Output is correct |
32 |
Correct |
1000 ms |
36136 KB |
Output is correct |
33 |
Correct |
996 ms |
35912 KB |
Output is correct |
34 |
Correct |
1169 ms |
61088 KB |
Output is correct |
35 |
Correct |
908 ms |
53448 KB |
Output is correct |
36 |
Correct |
655 ms |
1856 KB |
Output is correct |
37 |
Correct |
6 ms |
1288 KB |
Output is correct |
38 |
Correct |
652 ms |
1824 KB |
Output is correct |
39 |
Correct |
675 ms |
1816 KB |
Output is correct |
40 |
Correct |
588 ms |
1720 KB |
Output is correct |
41 |
Correct |
676 ms |
17584 KB |
Output is correct |
42 |
Correct |
642 ms |
1712 KB |
Output is correct |
43 |
Correct |
608 ms |
18064 KB |
Output is correct |
44 |
Correct |
794 ms |
2112 KB |
Output is correct |
45 |
Correct |
374 ms |
1744 KB |
Output is correct |
46 |
Correct |
1116 ms |
43968 KB |
Output is correct |
47 |
Correct |
1030 ms |
43776 KB |
Output is correct |
48 |
Correct |
1511 ms |
75208 KB |
Output is correct |
49 |
Correct |
1072 ms |
64520 KB |
Output is correct |
50 |
Correct |
640 ms |
2016 KB |
Output is correct |
51 |
Correct |
634 ms |
1960 KB |
Output is correct |
52 |
Correct |
654 ms |
1760 KB |
Output is correct |
53 |
Correct |
1106 ms |
42016 KB |
Output is correct |
54 |
Correct |
744 ms |
1760 KB |
Output is correct |
55 |
Correct |
1194 ms |
37216 KB |
Output is correct |
56 |
Correct |
900 ms |
1568 KB |
Output is correct |
57 |
Correct |
806 ms |
2000 KB |
Output is correct |
58 |
Correct |
582 ms |
1592 KB |
Output is correct |
59 |
Correct |
1432 ms |
49328 KB |
Output is correct |
60 |
Correct |
1380 ms |
49232 KB |
Output is correct |
61 |
Correct |
1658 ms |
85344 KB |
Output is correct |
62 |
Correct |
1354 ms |
78472 KB |
Output is correct |
63 |
Correct |
974 ms |
2272 KB |
Output is correct |
64 |
Correct |
872 ms |
2056 KB |
Output is correct |
65 |
Correct |
1531 ms |
46768 KB |
Output is correct |
66 |
Correct |
1586 ms |
41008 KB |
Output is correct |
67 |
Correct |
922 ms |
2272 KB |
Output is correct |
68 |
Correct |
926 ms |
2272 KB |
Output is correct |
69 |
Correct |
2258 ms |
83408 KB |
Output is correct |
70 |
Correct |
1786 ms |
67896 KB |
Output is correct |
71 |
Correct |
1128 ms |
9352 KB |
Output is correct |
72 |
Correct |
856 ms |
2648 KB |
Output is correct |