oj.uz

Submission #943718

# Submission time Handle Problem Language Result Execution time Memory
943718 2024-03-11T18:37:58 Z yeediot Two Transportations (JOI19_transportations) C++14
0 / 100
 419 ms 58924 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,cnt,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();
            cur=bit=0;
        }
        else{
            mn.F=cur;
            first=1;
            cur=bit=0;
        }
    }
    void gid(){
        mn.S=cur;
        gmn();
        cur=bit=0;
        first=0;
    }
}  // 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]-prv,i});
    }
    send(mn.F,9);
}

void ReceiveA(bool x) {
    cur=cur*2+x;
    bit++;
    if(bit==9 and first==0){
        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:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     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 419 ms 24264 KB Output is correct
2 Runtime error 209 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 169 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 369 ms 24328 KB Output is correct
2 Runtime error 169 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 148 ms 24288 KB Output is correct
2 Correct 130 ms 24256 KB Output is correct
3 Correct 236 ms 36828 KB Output is correct
4 Correct 179 ms 24216 KB Output is correct
5 Correct 216 ms 33408 KB Output is correct
6 Correct 176 ms 24296 KB Output is correct
7 Correct 186 ms 24216 KB Output is correct
8 Correct 142 ms 24328 KB Output is correct
9 Correct 253 ms 41856 KB Output is correct
10 Correct 196 ms 41612 KB Output is correct
11 Correct 359 ms 58924 KB Output is correct
12 Correct 318 ms 54296 KB Output is correct
13 Correct 167 ms 24216 KB Output is correct
14 Runtime error 178 ms 12168 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 148 ms 24288 KB Output is correct
2 Correct 130 ms 24256 KB Output is correct
3 Correct 236 ms 36828 KB Output is correct
4 Correct 179 ms 24216 KB Output is correct
5 Correct 216 ms 33408 KB Output is correct
6 Correct 176 ms 24296 KB Output is correct
7 Correct 186 ms 24216 KB Output is correct
8 Correct 142 ms 24328 KB Output is correct
9 Correct 253 ms 41856 KB Output is correct
10 Correct 196 ms 41612 KB Output is correct
11 Correct 359 ms 58924 KB Output is correct
12 Correct 318 ms 54296 KB Output is correct
13 Correct 167 ms 24216 KB Output is correct
14 Runtime error 178 ms 12168 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 148 ms 24288 KB Output is correct
2 Correct 130 ms 24256 KB Output is correct
3 Correct 236 ms 36828 KB Output is correct
4 Correct 179 ms 24216 KB Output is correct
5 Correct 216 ms 33408 KB Output is correct
6 Correct 176 ms 24296 KB Output is correct
7 Correct 186 ms 24216 KB Output is correct
8 Correct 142 ms 24328 KB Output is correct
9 Correct 253 ms 41856 KB Output is correct
10 Correct 196 ms 41612 KB Output is correct
11 Correct 359 ms 58924 KB Output is correct
12 Correct 318 ms 54296 KB Output is correct
13 Correct 167 ms 24216 KB Output is correct
14 Runtime error 178 ms 12168 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 419 ms 24264 KB Output is correct
2 Runtime error 209 ms 12164 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -