oj.uz

Submission #897324

# Submission time Handle Problem Language Result Execution time Memory
897324 2024-01-02T22:11:41 Z guagua0407 Two Transportations (JOI19_transportations) C++17
100 / 100
 544 ms 72428 KB 
#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace {

    const int inf=1e9;
    const int mxn=5e5+5;
    int n;
    vector<pair<int,int>> adj[mxn];
    int cur=0;
    int bit=0;
    int prv=0;
    int sir=0;
    int cnt=0;
    vector<int> d;
    vector<bool> vis;
    pair<int,int> mn={511,511};
    void send(int x,int len){
        for(int i=len-1;i>=0;i--){
            if(x&(1<<i)){
                SendA(1);
            }
            else{
                SendA(0);
            }
        }
    }
    void relax(){
        d[mn.s]=prv+mn.f;
        prv=d[mn.s];
        vis[mn.s]=true;
        cnt++;
        for(auto u:adj[mn.s]){
            d[u.f]=min(d[u.f],d[mn.s]+u.s);
        }
        mn={511,511};
        for(int i=0;i<n;i++){
            if(vis[i]) continue;
            mn=min(mn,{d[i]-prv,i});
        }
        if(cnt<n){
            send(mn.f,9);
        }
    }

    void getdis(){
        if(cur==511){
            send(mn.s,11);
            relax();
            cur=bit=0;
        }
        else{
            mn.f=cur;
            bit=cur=0;
            sir=1;
        }
    }

    void getid(){
        mn.s=cur;
        relax();
        bit=cur=0;
        sir=0;
    }
}  // namespace

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
    n=N;
    for(int i=0;i<A;i++){
        int a=U[i];
        int b=V[i];
        int c=C[i];
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    d=vector<int>(n,inf);
    vis=vector<bool>(n,false);
    d[0]=0;
    vis[0]=true;
    cnt++;
    for(auto u:adj[0]){
        d[u.f]=min(d[u.f],d[0]+u.s);
    }
    for(int i=0;i<n;i++){
        if(vis[i]) continue;
        mn=min(mn,{d[i]-prv,i});
    }
    send(mn.f,9);
}

void ReceiveA(bool x) {
    cur=cur*2+x;
    bit++;
    if(bit==9 and sir==0){
        getdis();
    }
    else if(bit==11){
        getid();
    }
}

std::vector<int> Answer() {
    return d;
}

#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace {

    const int inf=1e9;
    const int mxn=5e5+5;
    int n;
    vector<pair<int,int>> adj[mxn];
    int cur=0;
    int bit=0;
    int prv=0;
    int sir=0;
    vector<int> d;
    vector<bool> vis;
    pair<int,int> mn={511,511};
    void send(int x,int len){
        for(int i=len-1;i>=0;i--){
            if(x&(1<<i)){
                SendB(1);
            }
            else{
                SendB(0);
            }
        }
    }
    void relax(){
        d[mn.s]=prv+mn.f;
        prv=d[mn.s];
        vis[mn.s]=true;
        for(auto u:adj[mn.s]){
            d[u.f]=min(d[u.f],d[mn.s]+u.s);
        }
        mn={511,511};
        for(int i=0;i<n;i++){
            if(vis[i]) continue;
            mn=min(mn,{d[i]-prv,i});
        }
    }

    void getdis(){
        if(mn.f>cur){
            mn.f=cur;
            send(511,9);
            cur=bit=0;
            sir=1;
        }
        else{
            send(mn.f,9);
            send(mn.s,11);
            relax();
            cur=bit=0;
        }
    }

    void getid(){
        mn.s=cur;
        relax();
        bit=cur=0;
        sir=0;
    }
}  // namespace

void InitB(int N, int B, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
    n=N;
    for(int i=0;i<B;i++){
        int a=U[i];
        int b=V[i];
        int c=C[i];
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    d=vector<int>(n,inf);
    vis=vector<bool>(n,false);
    d[0]=0;
    vis[0]=true;
    for(auto u:adj[0]){
        d[u.f]=min(d[u.f],d[0]+u.s);
    }
    for(int i=0;i<n;i++){
        if(vis[i]) continue;
        mn=min(mn,{d[i]-prv,i});
    }
}

void ReceiveB(bool x) {
    cur=cur*2+x;
    bit++;
    if(bit==9 and sir==0){
        getdis();
    }
    else if(bit==11){
        getid();
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 24260 KB Output is correct
2 Correct 6 ms 24472 KB Output is correct
3 Correct 391 ms 24264 KB Output is correct
4 Correct 377 ms 33920 KB Output is correct
5 Correct 19 ms 24472 KB Output is correct
6 Correct 344 ms 25852 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 24276 KB Output is correct
2 Correct 293 ms 24352 KB Output is correct
3 Correct 306 ms 24408 KB Output is correct
4 Correct 409 ms 51160 KB Output is correct
5 Correct 423 ms 47580 KB Output is correct
6 Correct 61 ms 24252 KB Output is correct
7 Correct 428 ms 48172 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 24332 KB Output is correct
2 Correct 8 ms 24272 KB Output is correct
3 Correct 289 ms 24512 KB Output is correct
4 Correct 282 ms 24352 KB Output is correct
5 Correct 319 ms 24352 KB Output is correct
6 Correct 290 ms 24332 KB Output is correct
7 Correct 302 ms 24352 KB Output is correct
8 Correct 291 ms 24272 KB Output is correct
9 Correct 382 ms 24264 KB Output is correct
10 Correct 341 ms 24520 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 24292 KB Output is correct
2 Correct 147 ms 24468 KB Output is correct
3 Correct 208 ms 37040 KB Output is correct
4 Correct 133 ms 24216 KB Output is correct
5 Correct 212 ms 33440 KB Output is correct
6 Correct 118 ms 24304 KB Output is correct
7 Correct 164 ms 24216 KB Output is correct
8 Correct 138 ms 24328 KB Output is correct
9 Correct 250 ms 41956 KB Output is correct
10 Correct 265 ms 41872 KB Output is correct
11 Correct 306 ms 59388 KB Output is correct
12 Correct 320 ms 54052 KB Output is correct
13 Correct 172 ms 24216 KB Output is correct
14 Correct 6 ms 24276 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 24292 KB Output is correct
2 Correct 147 ms 24468 KB Output is correct
3 Correct 208 ms 37040 KB Output is correct
4 Correct 133 ms 24216 KB Output is correct
5 Correct 212 ms 33440 KB Output is correct
6 Correct 118 ms 24304 KB Output is correct
7 Correct 164 ms 24216 KB Output is correct
8 Correct 138 ms 24328 KB Output is correct
9 Correct 250 ms 41956 KB Output is correct
10 Correct 265 ms 41872 KB Output is correct
11 Correct 306 ms 59388 KB Output is correct
12 Correct 320 ms 54052 KB Output is correct
13 Correct 172 ms 24216 KB Output is correct
14 Correct 6 ms 24276 KB Output is correct
15 Correct 196 ms 24228 KB Output is correct
16 Correct 222 ms 24216 KB Output is correct
17 Correct 176 ms 24224 KB Output is correct
18 Correct 263 ms 33552 KB Output is correct
19 Correct 190 ms 24216 KB Output is correct
20 Correct 242 ms 33896 KB Output is correct
21 Correct 154 ms 24216 KB Output is correct
22 Correct 210 ms 24340 KB Output is correct
23 Correct 335 ms 45816 KB Output is correct
24 Correct 315 ms 45992 KB Output is correct
25 Correct 399 ms 67048 KB Output is correct
26 Correct 317 ms 60152 KB Output is correct
27 Correct 170 ms 24360 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 24292 KB Output is correct
2 Correct 147 ms 24468 KB Output is correct
3 Correct 208 ms 37040 KB Output is correct
4 Correct 133 ms 24216 KB Output is correct
5 Correct 212 ms 33440 KB Output is correct
6 Correct 118 ms 24304 KB Output is correct
7 Correct 164 ms 24216 KB Output is correct
8 Correct 138 ms 24328 KB Output is correct
9 Correct 250 ms 41956 KB Output is correct
10 Correct 265 ms 41872 KB Output is correct
11 Correct 306 ms 59388 KB Output is correct
12 Correct 320 ms 54052 KB Output is correct
13 Correct 172 ms 24216 KB Output is correct
14 Correct 6 ms 24276 KB Output is correct
15 Correct 196 ms 24228 KB Output is correct
16 Correct 222 ms 24216 KB Output is correct
17 Correct 176 ms 24224 KB Output is correct
18 Correct 263 ms 33552 KB Output is correct
19 Correct 190 ms 24216 KB Output is correct
20 Correct 242 ms 33896 KB Output is correct
21 Correct 154 ms 24216 KB Output is correct
22 Correct 210 ms 24340 KB Output is correct
23 Correct 335 ms 45816 KB Output is correct
24 Correct 315 ms 45992 KB Output is correct
25 Correct 399 ms 67048 KB Output is correct
26 Correct 317 ms 60152 KB Output is correct
27 Correct 170 ms 24360 KB Output is correct
28 Correct 207 ms 24312 KB Output is correct
29 Correct 229 ms 24516 KB Output is correct
30 Correct 352 ms 47612 KB Output is correct
31 Correct 228 ms 24260 KB Output is correct
32 Correct 309 ms 44632 KB Output is correct
33 Correct 228 ms 24340 KB Output is correct
34 Correct 270 ms 24364 KB Output is correct
35 Correct 209 ms 24368 KB Output is correct
36 Correct 327 ms 48352 KB Output is correct
37 Correct 351 ms 48564 KB Output is correct
38 Correct 544 ms 72428 KB Output is correct
39 Correct 448 ms 67756 KB Output is correct
40 Correct 252 ms 24216 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 24260 KB Output is correct
2 Correct 6 ms 24472 KB Output is correct
3 Correct 391 ms 24264 KB Output is correct
4 Correct 377 ms 33920 KB Output is correct
5 Correct 19 ms 24472 KB Output is correct
6 Correct 344 ms 25852 KB Output is correct
7 Correct 8 ms 24276 KB Output is correct
8 Correct 293 ms 24352 KB Output is correct
9 Correct 306 ms 24408 KB Output is correct
10 Correct 409 ms 51160 KB Output is correct
11 Correct 423 ms 47580 KB Output is correct
12 Correct 61 ms 24252 KB Output is correct
13 Correct 428 ms 48172 KB Output is correct
14 Correct 279 ms 24332 KB Output is correct
15 Correct 8 ms 24272 KB Output is correct
16 Correct 289 ms 24512 KB Output is correct
17 Correct 282 ms 24352 KB Output is correct
18 Correct 319 ms 24352 KB Output is correct
19 Correct 290 ms 24332 KB Output is correct
20 Correct 302 ms 24352 KB Output is correct
21 Correct 291 ms 24272 KB Output is correct
22 Correct 382 ms 24264 KB Output is correct
23 Correct 341 ms 24520 KB Output is correct
24 Correct 157 ms 24292 KB Output is correct
25 Correct 147 ms 24468 KB Output is correct
26 Correct 208 ms 37040 KB Output is correct
27 Correct 133 ms 24216 KB Output is correct
28 Correct 212 ms 33440 KB Output is correct
29 Correct 118 ms 24304 KB Output is correct
30 Correct 164 ms 24216 KB Output is correct
31 Correct 138 ms 24328 KB Output is correct
32 Correct 250 ms 41956 KB Output is correct
33 Correct 265 ms 41872 KB Output is correct
34 Correct 306 ms 59388 KB Output is correct
35 Correct 320 ms 54052 KB Output is correct
36 Correct 172 ms 24216 KB Output is correct
37 Correct 6 ms 24276 KB Output is correct
38 Correct 196 ms 24228 KB Output is correct
39 Correct 222 ms 24216 KB Output is correct
40 Correct 176 ms 24224 KB Output is correct
41 Correct 263 ms 33552 KB Output is correct
42 Correct 190 ms 24216 KB Output is correct
43 Correct 242 ms 33896 KB Output is correct
44 Correct 154 ms 24216 KB Output is correct
45 Correct 210 ms 24340 KB Output is correct
46 Correct 335 ms 45816 KB Output is correct
47 Correct 315 ms 45992 KB Output is correct
48 Correct 399 ms 67048 KB Output is correct
49 Correct 317 ms 60152 KB Output is correct
50 Correct 170 ms 24360 KB Output is correct
51 Correct 207 ms 24312 KB Output is correct
52 Correct 229 ms 24516 KB Output is correct
53 Correct 352 ms 47612 KB Output is correct
54 Correct 228 ms 24260 KB Output is correct
55 Correct 309 ms 44632 KB Output is correct
56 Correct 228 ms 24340 KB Output is correct
57 Correct 270 ms 24364 KB Output is correct
58 Correct 209 ms 24368 KB Output is correct
59 Correct 327 ms 48352 KB Output is correct
60 Correct 351 ms 48564 KB Output is correct
61 Correct 544 ms 72428 KB Output is correct
62 Correct 448 ms 67756 KB Output is correct
63 Correct 252 ms 24216 KB Output is correct
64 Correct 338 ms 24432 KB Output is correct
65 Correct 463 ms 50172 KB Output is correct
66 Correct 431 ms 46800 KB Output is correct
67 Correct 302 ms 24412 KB Output is correct
68 Correct 291 ms 24408 KB Output is correct
69 Correct 542 ms 71140 KB Output is correct
70 Correct 540 ms 63048 KB Output is correct
71 Correct 315 ms 28464 KB Output is correct
72 Correct 287 ms 24984 KB Output is correct