oj.uz

Submission #943734

# Submission time Handle Problem Language Result Execution time Memory
943734 2024-03-11T18:52:25 Z yeediot Two Transportations (JOI19_transportations) C++14
0 / 100
 395 ms 58972 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;
    vector<pair<int,int>>adj[mxn];
    vector<int>dis;
    vector<bool>vis;
    int prev=0;
    bool first=1;
    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]=prev+mn.F;
        prev=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]-prev,i});
        }
        if(cnt)send(mn.F,9);
    }
    void gdis(){
        if(cur==(1<<9)-1){
            send(mn.S,11);
            gmn();
            first=1;
        }
        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);
    vis=vector<bool>(N);
    dis[0]=0;
    vis[0]=1;
    cnt--;
    for(int i=1;i<N;i++){
        dis[i]=1e9;
        vis[i]=0;
    }
    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;
    vector<pair<int,int>>adj[mxn];
    vector<int>dis;
    int prev=0;
    vector<bool>vis;
    bool first=1;
    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]=prev+mn.F;
        prev=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]-prev,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);
    vis=vector<bool>(N);
    dis[0]=0;
    vis[0]=1;
    for(int i=1;i<N;i++){
        dis[i]=1e9;
        vis[i]=0;
    }
    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

Azer.cpp: In function 'void {anonymous}::gmn()':
Azer.cpp:26:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |         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:72:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |     for(auto [u,d]:adj[v]){
      |              ^

Baijan.cpp: In function 'void {anonymous}::gmn()':
Baijan.cpp:25:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |         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:69:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for(auto [u,d]:adj[v]){
      |              ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 24268 KB Output is correct
2 Runtime error 207 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 195 ms 12172 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 395 ms 24328 KB Output is correct
2 Runtime error 175 ms 12164 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 155 ms 24216 KB Output is correct
2 Correct 181 ms 24276 KB Output is correct
3 Correct 263 ms 37136 KB Output is correct
4 Correct 180 ms 24312 KB Output is correct
5 Correct 232 ms 33564 KB Output is correct
6 Correct 174 ms 24300 KB Output is correct
7 Correct 150 ms 24216 KB Output is correct
8 Correct 175 ms 24328 KB Output is correct
9 Correct 263 ms 41820 KB Output is correct
10 Correct 272 ms 41608 KB Output is correct
11 Correct 335 ms 58972 KB Output is correct
12 Correct 275 ms 54516 KB Output is correct
13 Correct 158 ms 24216 KB Output is correct
14 Runtime error 176 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 155 ms 24216 KB Output is correct
2 Correct 181 ms 24276 KB Output is correct
3 Correct 263 ms 37136 KB Output is correct
4 Correct 180 ms 24312 KB Output is correct
5 Correct 232 ms 33564 KB Output is correct
6 Correct 174 ms 24300 KB Output is correct
7 Correct 150 ms 24216 KB Output is correct
8 Correct 175 ms 24328 KB Output is correct
9 Correct 263 ms 41820 KB Output is correct
10 Correct 272 ms 41608 KB Output is correct
11 Correct 335 ms 58972 KB Output is correct
12 Correct 275 ms 54516 KB Output is correct
13 Correct 158 ms 24216 KB Output is correct
14 Runtime error 176 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 155 ms 24216 KB Output is correct
2 Correct 181 ms 24276 KB Output is correct
3 Correct 263 ms 37136 KB Output is correct
4 Correct 180 ms 24312 KB Output is correct
5 Correct 232 ms 33564 KB Output is correct
6 Correct 174 ms 24300 KB Output is correct
7 Correct 150 ms 24216 KB Output is correct
8 Correct 175 ms 24328 KB Output is correct
9 Correct 263 ms 41820 KB Output is correct
10 Correct 272 ms 41608 KB Output is correct
11 Correct 335 ms 58972 KB Output is correct
12 Correct 275 ms 54516 KB Output is correct
13 Correct 158 ms 24216 KB Output is correct
14 Runtime error 176 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 394 ms 24268 KB Output is correct
2 Runtime error 207 ms 12168 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -