oj.uz

Submission #943719

# Submission time Handle Problem Language Result Execution time Memory
943719 2024-03-11T18:38:44 Z yeediot Two Transportations (JOI19_transportations) C++14
0 / 100
 431 ms 59008 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,cnt=0,prv=0,first=1;
    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);
            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 409 ms 24264 KB Output is correct
2 Runtime error 175 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 197 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 431 ms 24332 KB Output is correct
2 Runtime error 194 ms 12152 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 167 ms 24288 KB Output is correct
2 Correct 181 ms 24468 KB Output is correct
3 Correct 197 ms 36836 KB Output is correct
4 Correct 146 ms 24308 KB Output is correct
5 Correct 199 ms 33660 KB Output is correct
6 Correct 192 ms 24220 KB Output is correct
7 Correct 166 ms 24216 KB Output is correct
8 Correct 115 ms 24324 KB Output is correct
9 Correct 215 ms 41604 KB Output is correct
10 Correct 274 ms 41832 KB Output is correct
11 Correct 371 ms 59008 KB Output is correct
12 Correct 291 ms 54412 KB Output is correct
13 Correct 149 ms 24216 KB Output is correct
14 Runtime error 168 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 167 ms 24288 KB Output is correct
2 Correct 181 ms 24468 KB Output is correct
3 Correct 197 ms 36836 KB Output is correct
4 Correct 146 ms 24308 KB Output is correct
5 Correct 199 ms 33660 KB Output is correct
6 Correct 192 ms 24220 KB Output is correct
7 Correct 166 ms 24216 KB Output is correct
8 Correct 115 ms 24324 KB Output is correct
9 Correct 215 ms 41604 KB Output is correct
10 Correct 274 ms 41832 KB Output is correct
11 Correct 371 ms 59008 KB Output is correct
12 Correct 291 ms 54412 KB Output is correct
13 Correct 149 ms 24216 KB Output is correct
14 Runtime error 168 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 167 ms 24288 KB Output is correct
2 Correct 181 ms 24468 KB Output is correct
3 Correct 197 ms 36836 KB Output is correct
4 Correct 146 ms 24308 KB Output is correct
5 Correct 199 ms 33660 KB Output is correct
6 Correct 192 ms 24220 KB Output is correct
7 Correct 166 ms 24216 KB Output is correct
8 Correct 115 ms 24324 KB Output is correct
9 Correct 215 ms 41604 KB Output is correct
10 Correct 274 ms 41832 KB Output is correct
11 Correct 371 ms 59008 KB Output is correct
12 Correct 291 ms 54412 KB Output is correct
13 Correct 149 ms 24216 KB Output is correct
14 Runtime error 168 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 409 ms 24264 KB Output is correct
2 Runtime error 175 ms 12164 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -