oj.uz

Submission #943720

# Submission time Handle Problem Language Result Execution time Memory
943720 2024-03-11T18:40:19 Z yeediot Two Transportations (JOI19_transportations) C++14
0 / 100
 432 ms 59216 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={511,511};
    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={511,511};
        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==511){
            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,prv=0,first=0;
    vector<pair<int,int>>adj[mxn];
    vector<int>dis;
    vector<bool>vis;
    pair<int,int>mn={511,511};
    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={511,511};
        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(511,9);
            cur=bit=0;
            first=1;
        }
        else{
            send(mn.F,9);
            send(mn.S,11);
            gmn();
            cur=bit=0;
        }
    }
    void gid(){
        mn.S=cur;
        gmn();
        cur=bit=0;
        first=0;
    }
}  // 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==0){
        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:64:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |     for(auto [u,d]:adj[v]){
      |              ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 24264 KB Output is correct
2 Runtime error 219 ms 12168 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 189 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 432 ms 24332 KB Output is correct
2 Runtime error 210 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 160 ms 24216 KB Output is correct
2 Correct 162 ms 24264 KB Output is correct
3 Correct 228 ms 36848 KB Output is correct
4 Correct 152 ms 24216 KB Output is correct
5 Correct 219 ms 33604 KB Output is correct
6 Correct 194 ms 24216 KB Output is correct
7 Correct 205 ms 24216 KB Output is correct
8 Correct 173 ms 24216 KB Output is correct
9 Correct 300 ms 41688 KB Output is correct
10 Correct 304 ms 41772 KB Output is correct
11 Correct 326 ms 59216 KB Output is correct
12 Correct 326 ms 54308 KB Output is correct
13 Correct 146 ms 24216 KB Output is correct
14 Runtime error 221 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 160 ms 24216 KB Output is correct
2 Correct 162 ms 24264 KB Output is correct
3 Correct 228 ms 36848 KB Output is correct
4 Correct 152 ms 24216 KB Output is correct
5 Correct 219 ms 33604 KB Output is correct
6 Correct 194 ms 24216 KB Output is correct
7 Correct 205 ms 24216 KB Output is correct
8 Correct 173 ms 24216 KB Output is correct
9 Correct 300 ms 41688 KB Output is correct
10 Correct 304 ms 41772 KB Output is correct
11 Correct 326 ms 59216 KB Output is correct
12 Correct 326 ms 54308 KB Output is correct
13 Correct 146 ms 24216 KB Output is correct
14 Runtime error 221 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 160 ms 24216 KB Output is correct
2 Correct 162 ms 24264 KB Output is correct
3 Correct 228 ms 36848 KB Output is correct
4 Correct 152 ms 24216 KB Output is correct
5 Correct 219 ms 33604 KB Output is correct
6 Correct 194 ms 24216 KB Output is correct
7 Correct 205 ms 24216 KB Output is correct
8 Correct 173 ms 24216 KB Output is correct
9 Correct 300 ms 41688 KB Output is correct
10 Correct 304 ms 41772 KB Output is correct
11 Correct 326 ms 59216 KB Output is correct
12 Correct 326 ms 54308 KB Output is correct
13 Correct 146 ms 24216 KB Output is correct
14 Runtime error 221 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 358 ms 24264 KB Output is correct
2 Runtime error 219 ms 12168 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -