oj.uz

Submission #943693

# Submission time Handle Problem Language Result Execution time Memory
943693 2024-03-11T18:08:04 Z yeediot Two Transportations (JOI19_transportations) C++17
0 / 100
 346 ms 59368 KB 
#include "Azer.h"
#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
namespace {
    const int mxn=5e5+5;
    int cur=0,bit=0,n=0,cnt=0,prv=0,first=0;
    vector<pair<int,int>>adj[mxn];
    vector<int>dis;
    vector<bool>vis;
    pair<int,int>mn={(1<<9)-1,(1<<9)-1};
    void send(int a,int b){
        b--;
        for(;b>=0;b--){
            SendA(a>>b&1);
        }
    }
    void gmn(){
        dis[mn.S]=prv+mn.F;
        prv=dis[mn.S];
        cnt--;
        vis[mn.S]=1;
        for(auto [u,d]:adj[mn.S]){
            dis[u]=min(dis[u],dis[mn.S]+d);
        }
        mn={(1<<9)-1,(1<<9)-1};
        for(int i=0;i<n;i++){
            if(vis[i])continue;
            mn=min(mn,{dis[i]-prv,i});
        }
        if(cnt)send(mn.F,9);
    }
    void gdis(){
        if(cur==(1<<9)-1){
            send(mn.S,11);
            gmn();
        }
        else{
            mn.F=cur;
            first=0;
        }
        cur=bit=0;
    }
    void gid(){
        mn.S=cur;
        gmn();
        cur=bit=0;
        first=1;
    }
}  // namespace
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,std::vector<int> C) {
    for(int i=0;i<A;i++){
        adj[V[i]].push_back({U[i],C[i]});
        adj[U[i]].push_back({V[i],C[i]});
    }
    n=N;
    cnt=n;
    first=1;
    bit=0;
    cur=0;
    prv=0;
    dis=vector<int>(N,1e9);
    vis=vector<bool>(N,0);
    dis[0]=0;
    vis[0]=1;
    cnt--;
    int v=0;
    for(auto [u,d]:adj[v]){
        dis[u]=min(dis[u],dis[v]+d);
        mn=min(mn,{dis[u],u});
    }
    send(mn.F,9);
}

void ReceiveA(bool x) {
    cur=cur*2+x;
    bit++;
    if(bit==9 and first){
        gdis();
    }
    else if(bit==11){
        gid();
    }
}

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

#include "Baijan.h"
#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
namespace {
    const int mxn=5e5+5;
    int cur=0,bit=0,n=0,cnt=0,prv=0,first=0;
    vector<pair<int,int>>adj[mxn];
    vector<int>dis;
    vector<bool>vis;
    pair<int,int>mn={(1<<9)-1,(1<<9)-1};
    void send(int a,int b){
        b--;
        for(;b>=0;b--){
            SendB(a>>b&1);
        }
    }
    void gmn(){
        dis[mn.S]=prv+mn.F;
        prv=dis[mn.S];
        vis[mn.S]=1;
        for(auto [u,d]:adj[mn.S]){
            dis[u]=min(dis[u],dis[mn.S]+d);
        }
        mn={(1<<9)-1,(1<<9)-1};
        for(int i=0;i<n;i++){
            if(vis[i])continue;
            mn=min(mn,{dis[i]-prv,i});
        }
    }
    void gdis(){
        if(mn.F>cur){
            mn.F=cur;
            send((1<<9)-1,9);
            first=0;
        }
        else{
            send(mn.F,9);
            send(mn.S,11);
            gmn();
        }
        cur=bit=0;
    }
    void gid(){
        mn.S=cur;
        gmn();
        cur=bit=0;
        first=1;
    }
}  // namespace
void InitB(int N, int B, std::vector<int> U, std::vector<int> V,std::vector<int> C) {
    for(int i=0;i<B;i++){
        adj[V[i]].push_back({U[i],C[i]});
        adj[U[i]].push_back({V[i],C[i]});
    }
    n=N;
    first=1;
    bit=0;
    cur=0;
    prv=0;
    dis=vector<int>(N,1e9);
    vis=vector<bool>(N,0);
    dis[0]=0;
    vis[0]=1;
    int v=0;
    for(auto [u,d]:adj[v]){
        dis[u]=min(dis[u],dis[v]+d);
        mn=min(mn,{dis[u],u});
    }
}
void ReceiveB(bool x) {
    cur=cur*2+x;
    bit++;
    if(bit==9 and first){
        gdis();
    }
    else if(bit==11){
        gid();
    }
}

Compilation message

Baijan.cpp:8:25: warning: '{anonymous}::cnt' defined but not used [-Wunused-variable]
    8 |     int cur=0,bit=0,n=0,cnt=0,prv=0,first=0;
      |                         ^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 24264 KB Output is correct
2 Runtime error 209 ms 12420 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 190 ms 12168 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 24332 KB Output is correct
2 Runtime error 202 ms 12168 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 24544 KB Output is correct
2 Correct 183 ms 24268 KB Output is correct
3 Correct 222 ms 36832 KB Output is correct
4 Correct 164 ms 24312 KB Output is correct
5 Correct 155 ms 33900 KB Output is correct
6 Correct 150 ms 24312 KB Output is correct
7 Correct 180 ms 24728 KB Output is correct
8 Correct 148 ms 24328 KB Output is correct
9 Correct 250 ms 41596 KB Output is correct
10 Correct 228 ms 41832 KB Output is correct
11 Correct 314 ms 59368 KB Output is correct
12 Correct 346 ms 54400 KB Output is correct
13 Correct 174 ms 24216 KB Output is correct
14 Runtime error 185 ms 12164 KB Execution killed with signal 13
15 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 24544 KB Output is correct
2 Correct 183 ms 24268 KB Output is correct
3 Correct 222 ms 36832 KB Output is correct
4 Correct 164 ms 24312 KB Output is correct
5 Correct 155 ms 33900 KB Output is correct
6 Correct 150 ms 24312 KB Output is correct
7 Correct 180 ms 24728 KB Output is correct
8 Correct 148 ms 24328 KB Output is correct
9 Correct 250 ms 41596 KB Output is correct
10 Correct 228 ms 41832 KB Output is correct
11 Correct 314 ms 59368 KB Output is correct
12 Correct 346 ms 54400 KB Output is correct
13 Correct 174 ms 24216 KB Output is correct
14 Runtime error 185 ms 12164 KB Execution killed with signal 13
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 24544 KB Output is correct
2 Correct 183 ms 24268 KB Output is correct
3 Correct 222 ms 36832 KB Output is correct
4 Correct 164 ms 24312 KB Output is correct
5 Correct 155 ms 33900 KB Output is correct
6 Correct 150 ms 24312 KB Output is correct
7 Correct 180 ms 24728 KB Output is correct
8 Correct 148 ms 24328 KB Output is correct
9 Correct 250 ms 41596 KB Output is correct
10 Correct 228 ms 41832 KB Output is correct
11 Correct 314 ms 59368 KB Output is correct
12 Correct 346 ms 54400 KB Output is correct
13 Correct 174 ms 24216 KB Output is correct
14 Runtime error 185 ms 12164 KB Execution killed with signal 13
15 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 344 ms 24264 KB Output is correct
2 Runtime error 209 ms 12420 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -