oj.uz

Submission #943723

# Submission time Handle Problem Language Result Execution time Memory
943723 2024-03-11T18:41:48 Z yeediot Two Transportations (JOI19_transportations) C++14
0 / 100
 430 ms 58920 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--){
            if(a&(1<<b)){
                SendA(1);
            }
            else{
                SendA(0);
            }
        }
    }
    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--){
            if(a&(1<<b)){
                SendB(1);
            }
            else{
                SendB(0);
            }
        }
    }
    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:29:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |         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:71:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |     for(auto [u,d]:adj[v]){
      |              ^

Baijan.cpp: In function 'void {anonymous}::gmn()':
Baijan.cpp:28:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   28 |         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 430 ms 24264 KB Output is correct
2 Runtime error 153 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 213 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 429 ms 24332 KB Output is correct
2 Runtime error 172 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 157 ms 24216 KB Output is correct
2 Correct 193 ms 24256 KB Output is correct
3 Correct 231 ms 36736 KB Output is correct
4 Correct 162 ms 24316 KB Output is correct
5 Correct 237 ms 33660 KB Output is correct
6 Correct 180 ms 24300 KB Output is correct
7 Correct 181 ms 24216 KB Output is correct
8 Correct 181 ms 24332 KB Output is correct
9 Correct 279 ms 41572 KB Output is correct
10 Correct 275 ms 41808 KB Output is correct
11 Correct 391 ms 58920 KB Output is correct
12 Correct 322 ms 54400 KB Output is correct
13 Correct 110 ms 24216 KB Output is correct
14 Runtime error 161 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 157 ms 24216 KB Output is correct
2 Correct 193 ms 24256 KB Output is correct
3 Correct 231 ms 36736 KB Output is correct
4 Correct 162 ms 24316 KB Output is correct
5 Correct 237 ms 33660 KB Output is correct
6 Correct 180 ms 24300 KB Output is correct
7 Correct 181 ms 24216 KB Output is correct
8 Correct 181 ms 24332 KB Output is correct
9 Correct 279 ms 41572 KB Output is correct
10 Correct 275 ms 41808 KB Output is correct
11 Correct 391 ms 58920 KB Output is correct
12 Correct 322 ms 54400 KB Output is correct
13 Correct 110 ms 24216 KB Output is correct
14 Runtime error 161 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 157 ms 24216 KB Output is correct
2 Correct 193 ms 24256 KB Output is correct
3 Correct 231 ms 36736 KB Output is correct
4 Correct 162 ms 24316 KB Output is correct
5 Correct 237 ms 33660 KB Output is correct
6 Correct 180 ms 24300 KB Output is correct
7 Correct 181 ms 24216 KB Output is correct
8 Correct 181 ms 24332 KB Output is correct
9 Correct 279 ms 41572 KB Output is correct
10 Correct 275 ms 41808 KB Output is correct
11 Correct 391 ms 58920 KB Output is correct
12 Correct 322 ms 54400 KB Output is correct
13 Correct 110 ms 24216 KB Output is correct
14 Runtime error 161 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 430 ms 24264 KB Output is correct
2 Runtime error 153 ms 12168 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -