# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
996868 |
2024-06-11T11:05:36 Z |
errorgorn |
Spy 3 (JOI24_spy3) |
C++17 |
|
118 ms |
81524 KB |
#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
namespace {
int n,m,q,k;
vector<ii> al[20005];
int w[20005];
int hidden[20005];
vector<ii> al2[20005];
ii pp[20005];
int d[20005];
int typ[20005];
int CNT=2;
int ID[1<<16];
string bs;
int inf[305];
int CNT2=0;
int posq[35];
void dfs(int i){
bool f=false;
if (ID[typ[i]]==-1){
ID[typ[i]]=CNT++;
f=true;
bs+="0";
}
if (n<=i){
//cout<<i<<" "<<ID[typ[i]]<<endl;
posq[i-n]=CNT2++;
}
for (auto [it,id]:al2[i]) if ((typ[it])&1){
if (typ[it]){
dfs(it);
if (hidden[id]!=-1) inf[hidden[id]]=ID[typ[it]];
//if (typ[it]!=typ[i]) cout<<"? "<<ID[typ[i]]<<" "<<ID[typ[it]]<<endl;
}
}
for (auto [it,id]:al2[i]) if ((~typ[it])&1){
if (typ[it]){
dfs(it);
if (hidden[id]!=-1) inf[hidden[id]]=ID[typ[it]];
//if (typ[it]!=typ[i]) cout<<"? "<<ID[typ[i]]<<" "<<ID[typ[it]]<<endl;
}
}
if (f) bs+="1";
}
} // namespace
std::string aoi(signed N, signed M, signed Q, signed K, std::vector<signed> A,
std::vector<signed> B, std::vector<long long> C,
std::vector<signed> T, std::vector<signed> X) {
n=N,m=M,q=Q,k=K;
rep(x,0,m){
al[A[x]].pub({B[x],x});
al[B[x]].pub({A[x],x});
w[x]=C[x];
}
memset(hidden,-1,sizeof(hidden));
rep(x,0,k) hidden[X[x]]=x;
priority_queue<ii,vector<ii>,greater<ii> > pq;
memset(d,63,sizeof(d));
d[0]=0;
pq.push({d[0],0});
while (!pq.empty()){
int u,ww; tie(ww,u)=pq.top(); pq.pop();
if (d[u]!=ww) continue;
for (auto [it,id]:al[u]) if (d[it]>ww+w[id]){
d[it]=ww+w[id];
pq.push({d[it],it});
pp[it]={u,id};
}
}
rep(x,1,n) al2[pp[x].fi].pub({x,pp[x].se});
rep(x,0,q){
int curr=T[x];
while (curr){
typ[curr]|=1<<x;
curr=pp[curr].fi;
}
al2[T[x]].pub({n+x,20004});
typ[n+x]=1<<x;
}
memset(ID,-1,sizeof(ID));
typ[0]=(1<<q)-1;
ID[(1<<q)-1]=1;
dfs(0);
//rep(x,0,n) cout<<typ[x]<<" "; cout<<endl;
//rep(x,0,k) cout<<inf[x]<<" "; cout<<endl;
string s;
rep(x,0,k){
rep(i,0,5) s+='0'+((inf[x]>>i)&1);
}
rep(x,1,q){
//cout<<d[T[x]]<<endl;
rep(i,0,4) s+='0'+((posq[x]>>i)&1);
}
if (bs=="") bs="01";
return s+bs.substr(1,sz(bs)-2);
}
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define fi first
#define se second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
namespace {
int n,m,q,k;
vector<ii> al[10005];
int w[20005];
vector<int> imp;
int rit[10005];
int d[610][10005];
ii pp[610][10005];
void add(int u){
int i=sz(imp);
rit[u]=i;
imp.pub(u);
priority_queue<ii,vector<ii>,greater<ii> > pq;
memset(d[i],63,sizeof(d[i]));
d[i][u]=0;
pq.push({d[i][u],u});
while (!pq.empty()){
int u,ww; tie(ww,u)=pq.top(); pq.pop();
if (d[i][u]!=ww) continue;
for (auto [it,id]:al[u]) if (d[i][it]>ww+w[id]){
d[i][it]=ww+w[id];
pq.push({d[i][it],it});
pp[i][it]={u,id};
}
}
}
int inf[305];
int sp[50];
ii PP[10005]; //this guys contains the actual answers
int RR[50];
} // namespace
void bitaro(signed N, signed M, signed Q, signed K, std::vector<signed> A, std::vector<signed> B,
std::vector<long long> C, std::vector<signed> T, std::vector<signed> X,
std::string s) {
n=N,m=M,q=Q,k=K;
rep(x,0,m) if (C[x]!=-1){
al[A[x]].pub({B[x],x});
al[B[x]].pub({A[x],x});
w[x]=C[x];
}
memset(rit,-1,sizeof(rit));
add(0);
rep(x,0,k){
rep(i,0,5) if (s[x*5+i]=='1') inf[x]+=1<<i;
}
int currn=2;
vector<int> stk={1};
string bs="0"+s.substr(k*5+(q-1)*4,sz(s)-(k*5+(q-1)*4))+"1";
sp[1]=0;
for (auto it:bs){
if (it=='0'){
sp[currn]=stk.back();
stk.pub(currn++);
}
else{
stk.pob();
}
}
vector<int> LL;
rep(x,1,currn){
bool leaf=true;
rep(y,1,currn) if (sp[y]==x) leaf=false;
if (leaf) LL.pub(x);
}
//for (auto it:LL) cout<<it<<" "; cout<<endl;
RR[0]=0;
add(0);
rep(x,1,currn){
set<int> st;
rep(y,0,k) if (inf[y]==x) st.insert(y);
int R=RR[sp[x]];
while (!st.empty()){
int mn=1e18;
for (auto it:st){
mn=min(mn,d[rit[R]][A[X[it]]]);
mn=min(mn,d[rit[R]][B[X[it]]]);
}
for (auto it:st){
if (mn==d[rit[R]][A[X[it]]]){
int curr=A[X[it]];
while (curr!=R){
PP[curr]={pp[rit[R]][curr].fi,pp[rit[R]][curr].se};
curr=pp[rit[R]][curr].fi;
}
PP[B[X[it]]]={A[X[it]],X[it]};
R=B[X[it]];
st.erase(it);
break;
}
if (mn==d[rit[R]][B[X[it]]]){
int curr=B[X[it]];
while (curr!=R){
PP[curr]={pp[rit[R]][curr].fi,pp[rit[R]][curr].se};
curr=pp[rit[R]][curr].fi;
}
PP[A[X[it]]]={B[X[it]],X[it]};
R=A[X[it]];
st.erase(it);
break;
}
}
if (rit[R]==-1) add(R);
}
RR[x]=R;
//cout<<"debug: "<<x<<" "<<R<<endl;
}
//rep(x,0,n) cout<<x<<" "<<PP[x].fi<<" "<<PP[x].se<<endl;
rep(x,0,q){
int grp=0;
if (x){
rep(i,0,4) if (s[k*5+(x-1)*4+i]=='1') grp+=1<<i;
}
grp=LL[grp];
int curr=T[x];
while (curr!=RR[grp]){
PP[curr]={pp[rit[RR[grp]]][curr].fi,pp[rit[RR[grp]]][curr].se};
curr=pp[rit[RR[grp]]][curr].fi;
}
vector<signed> stk;
curr=T[x];
while (curr){
stk.pub(PP[curr].se);
curr=PP[curr].fi;
}
reverse(all(stk));
//for (auto it:stk) cout<<it<<" "; cout<<endl;
answer(stk);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
12668 KB |
Output is correct |
2 |
Correct |
1 ms |
7180 KB |
Output is correct |
3 |
Partially correct |
76 ms |
31152 KB |
Partially correct |
4 |
Partially correct |
53 ms |
37792 KB |
Partially correct |
5 |
Partially correct |
16 ms |
12756 KB |
Partially correct |
6 |
Partially correct |
41 ms |
16820 KB |
Partially correct |
7 |
Partially correct |
59 ms |
25164 KB |
Partially correct |
8 |
Partially correct |
25 ms |
14812 KB |
Partially correct |
9 |
Partially correct |
47 ms |
35668 KB |
Partially correct |
10 |
Correct |
38 ms |
18868 KB |
Output is correct |
11 |
Partially correct |
32 ms |
16820 KB |
Partially correct |
12 |
Correct |
35 ms |
17072 KB |
Output is correct |
13 |
Correct |
51 ms |
16824 KB |
Output is correct |
14 |
Correct |
26 ms |
12816 KB |
Output is correct |
15 |
Correct |
27 ms |
15328 KB |
Output is correct |
16 |
Correct |
33 ms |
17108 KB |
Output is correct |
17 |
Partially correct |
91 ms |
62896 KB |
Partially correct |
18 |
Partially correct |
81 ms |
60764 KB |
Partially correct |
19 |
Partially correct |
16 ms |
13204 KB |
Partially correct |
20 |
Correct |
15 ms |
13200 KB |
Output is correct |
21 |
Partially correct |
17 ms |
13176 KB |
Partially correct |
22 |
Partially correct |
19 ms |
13316 KB |
Partially correct |
23 |
Correct |
20 ms |
13408 KB |
Output is correct |
24 |
Partially correct |
24 ms |
13224 KB |
Partially correct |
25 |
Partially correct |
23 ms |
23560 KB |
Partially correct |
26 |
Partially correct |
24 ms |
23488 KB |
Partially correct |
27 |
Correct |
2 ms |
9480 KB |
Output is correct |
28 |
Correct |
23 ms |
13336 KB |
Output is correct |
29 |
Partially correct |
16 ms |
34828 KB |
Partially correct |
30 |
Correct |
30 ms |
15424 KB |
Output is correct |
31 |
Correct |
36 ms |
13504 KB |
Output is correct |
32 |
Correct |
44 ms |
17408 KB |
Output is correct |
33 |
Correct |
19 ms |
12912 KB |
Output is correct |
34 |
Correct |
19 ms |
13336 KB |
Output is correct |
35 |
Correct |
23 ms |
13240 KB |
Output is correct |
36 |
Correct |
41 ms |
19684 KB |
Output is correct |
37 |
Correct |
18 ms |
81524 KB |
Output is correct |
38 |
Partially correct |
26 ms |
80564 KB |
Partially correct |
39 |
Correct |
19 ms |
49928 KB |
Output is correct |
40 |
Correct |
12 ms |
30484 KB |
Output is correct |
41 |
Partially correct |
118 ms |
25992 KB |
Partially correct |
42 |
Correct |
37 ms |
13572 KB |
Output is correct |
43 |
Correct |
22 ms |
13628 KB |
Output is correct |
44 |
Correct |
20 ms |
13460 KB |
Output is correct |
45 |
Partially correct |
17 ms |
73108 KB |
Partially correct |
46 |
Partially correct |
19 ms |
67516 KB |
Partially correct |
47 |
Correct |
15 ms |
16392 KB |
Output is correct |
48 |
Correct |
1 ms |
7180 KB |
Output is correct |
49 |
Correct |
2 ms |
7180 KB |
Output is correct |
50 |
Correct |
15 ms |
16824 KB |
Output is correct |
51 |
Partially correct |
2 ms |
9740 KB |
Partially correct |
52 |
Correct |
2 ms |
9484 KB |
Output is correct |
53 |
Correct |
11 ms |
12788 KB |
Output is correct |
54 |
Partially correct |
9 ms |
11372 KB |
Partially correct |
55 |
Correct |
15 ms |
11956 KB |
Output is correct |
56 |
Correct |
17 ms |
13292 KB |
Output is correct |
57 |
Partially correct |
22 ms |
13748 KB |
Partially correct |
58 |
Partially correct |
17 ms |
12312 KB |
Partially correct |
59 |
Correct |
20 ms |
13428 KB |
Output is correct |
60 |
Partially correct |
23 ms |
13456 KB |
Partially correct |
61 |
Correct |
23 ms |
13404 KB |
Output is correct |
62 |
Correct |
19 ms |
12904 KB |
Output is correct |
63 |
Correct |
23 ms |
13396 KB |
Output is correct |
64 |
Correct |
17 ms |
12820 KB |
Output is correct |
65 |
Correct |
10 ms |
12052 KB |
Output is correct |
66 |
Correct |
17 ms |
13500 KB |
Output is correct |
67 |
Correct |
11 ms |
11952 KB |
Output is correct |
68 |
Correct |
17 ms |
13596 KB |
Output is correct |
69 |
Correct |
1 ms |
7188 KB |
Output is correct |
70 |
Correct |
2 ms |
7188 KB |
Output is correct |
71 |
Correct |
2 ms |
9492 KB |
Output is correct |
72 |
Correct |
8 ms |
11280 KB |
Output is correct |
73 |
Partially correct |
11 ms |
11532 KB |
Partially correct |
74 |
Partially correct |
11 ms |
11508 KB |
Partially correct |
75 |
Correct |
11 ms |
11524 KB |
Output is correct |
76 |
Correct |
2 ms |
7180 KB |
Output is correct |
77 |
Correct |
15 ms |
12996 KB |
Output is correct |
78 |
Partially correct |
19 ms |
13048 KB |
Partially correct |
79 |
Correct |
22 ms |
13072 KB |
Output is correct |
80 |
Correct |
2 ms |
7176 KB |
Output is correct |
81 |
Correct |
28 ms |
12724 KB |
Output is correct |
82 |
Partially correct |
24 ms |
14772 KB |
Partially correct |
83 |
Correct |
27 ms |
12728 KB |
Output is correct |