oj.uz

Submission #943709

# Submission time Handle Problem Language Result Execution time Memory
943709 2024-03-11T18:31:57 Z yeediot Two Transportations (JOI19_transportations) C++14
0 / 100
 392 ms 58932 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=1;
    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;
        cur=bit=0;
        first=1;
        gmn();
    }
}  // 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;
    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);
    }
    for(int i=0;i<n;i++){
        if(vis[i])continue;
        mn=min(mn,{dis[i],i});
    }
    send(mn.F,9);
}

void ReceiveA(bool x) {
    cur=cur*2+x;
    bit++;
    if(bit==9 and first==1){
        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=1;
    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;
        cur=bit=0;
        first=1;
        gmn();
    }
}  // 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;
    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);
    }
    for(int i=0;i<n;i++){
        if(vis[i])continue;
        mn=min(mn,{dis[i],i});
    }
}
void ReceiveB(bool x) {
    cur=cur*2+x;
    bit++;
    if(bit==9 and first==1){
        gdis();
    }
    else if(bit==11){
        gid();
    }
}

Compilation message

Azer.cpp: In function 'void {anonymous}::gmn()':
Azer.cpp:24:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |         for(auto [u,d]:adj[mn.S]){
      |                  ^
Azer.cpp: In function 'void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Azer.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |     for(auto [u,d]:adj[v]){
      |              ^

Baijan.cpp: In function 'void {anonymous}::gmn()':
Baijan.cpp:23:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |         for(auto [u,d]:adj[mn.S]){
      |                  ^
Baijan.cpp: In function 'void InitB(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Baijan.cpp:63:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |     for(auto [u,d]:adj[v]){
      |              ^
Baijan.cpp: At global scope:
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=1;
      |                         ^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 24260 KB Output is correct
2 Runtime error 172 ms 12164 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 207 ms 12164 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 368 ms 24328 KB Output is correct
2 Runtime error 206 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 136 ms 24216 KB Output is correct
2 Correct 185 ms 24260 KB Output is correct
3 Correct 249 ms 36844 KB Output is correct
4 Correct 150 ms 24216 KB Output is correct
5 Correct 235 ms 33464 KB Output is correct
6 Correct 178 ms 24216 KB Output is correct
7 Correct 156 ms 24216 KB Output is correct
8 Correct 166 ms 24324 KB Output is correct
9 Correct 269 ms 41704 KB Output is correct
10 Correct 241 ms 41820 KB Output is correct
11 Correct 392 ms 58932 KB Output is correct
12 Correct 338 ms 54436 KB Output is correct
13 Correct 152 ms 24216 KB Output is correct
14 Runtime error 189 ms 12172 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 136 ms 24216 KB Output is correct
2 Correct 185 ms 24260 KB Output is correct
3 Correct 249 ms 36844 KB Output is correct
4 Correct 150 ms 24216 KB Output is correct
5 Correct 235 ms 33464 KB Output is correct
6 Correct 178 ms 24216 KB Output is correct
7 Correct 156 ms 24216 KB Output is correct
8 Correct 166 ms 24324 KB Output is correct
9 Correct 269 ms 41704 KB Output is correct
10 Correct 241 ms 41820 KB Output is correct
11 Correct 392 ms 58932 KB Output is correct
12 Correct 338 ms 54436 KB Output is correct
13 Correct 152 ms 24216 KB Output is correct
14 Runtime error 189 ms 12172 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 136 ms 24216 KB Output is correct
2 Correct 185 ms 24260 KB Output is correct
3 Correct 249 ms 36844 KB Output is correct
4 Correct 150 ms 24216 KB Output is correct
5 Correct 235 ms 33464 KB Output is correct
6 Correct 178 ms 24216 KB Output is correct
7 Correct 156 ms 24216 KB Output is correct
8 Correct 166 ms 24324 KB Output is correct
9 Correct 269 ms 41704 KB Output is correct
10 Correct 241 ms 41820 KB Output is correct
11 Correct 392 ms 58932 KB Output is correct
12 Correct 338 ms 54436 KB Output is correct
13 Correct 152 ms 24216 KB Output is correct
14 Runtime error 189 ms 12172 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 390 ms 24260 KB Output is correct
2 Runtime error 172 ms 12164 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -