oj.uz

Submission #630444

# Submission time Handle Problem Language Result Execution time Memory
630444 2022-08-16T11:22:44 Z colazcy Ceste (COCI17_ceste) C++17
160 / 160
 178 ms 596 KB 
#include <cstdio>
#include <cassert>
#include <vector>
#include <queue>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
using type = double;
constexpr int maxn = 2e3 + 100;
constexpr ll inf = 0x3f3f3f3f3f3f3f3f;

struct Vector{
    int x,y;
    Vector operator + (const Vector t)const{return Vector{x + t.x,y + t.y};}
};

int n,m;
type dis[maxn];
Vector vec[maxn];
std::vector<std::pair<int,Vector>> G[maxn];
struct Node{
    int u;
    type h;
    bool operator < (const Node t)const{
        return h > t.h;
    }
};
ll ans[maxn];
void dij(const type t){ // t * x + (1 - t) * y
    static bool vis[maxn];
    static std::priority_queue<Node> q;
    std::fill_n(dis + 1,n,1e9);
    std::fill_n(vec + 1,n,Vector{0x7fffffff,0x7fffffff});
    std::fill_n(vis + 1,n,false);
    vec[1] = Vector{0,0}; dis[1] = 0; q.push(Node{1,0});
    while(!q.empty()){
        let u = q.top().u; q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(let &pir : G[u]){
            let v = pir.first;
            let w = pir.second;
            let m = t * w.x + (1 - t) * w.y;
            if(dis[u] + m < dis[v]){
                dis[v] = dis[u] + m;
                vec[v] = vec[u] + w;
                q.push(Node{v,dis[v]});
            }
        }
    }
    rep(i,2,n)ans[i] = std::min(ans[i],1ll * vec[i].x * vec[i].y);
}
int main(){
    std::scanf("%d %d",&n,&m);
    std::fill_n(ans + 1,n,inf);
    repn(m){
        int u,v,t,c; std::scanf("%d %d %d %d",&u,&v,&t,&c);
        G[u].emplace_back(v,Vector{t,c});
        G[v].emplace_back(u,Vector{t,c});     
    }
    type x = 0;
    while(x <= 1.0){
        dij(x);
        type nxt = 1e9;
        rep(u,1,n)
            for(let &pir : G[u]){
                let v = pir.first;
                let w = pir.second;
                let p = (-vec[u].y + vec[v].y - w.y);
                let q = (vec[u].x - vec[u].y + w.x - w.y - vec[v].x + vec[v].y);
                let s = type(p) / q;
                if(s > x)nxt = std::min(nxt,s);
            }
        x = nxt;
    }
    rep(i,2,n)std::printf("%lld\n",ans[i] >= inf ? -1 : ans[i]);
    return 0;
}

Compilation message

ceste.cpp: In function 'int main()':
ceste.cpp:58:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     std::scanf("%d %d",&n,&m);
      |     ~~~~~~~~~~^~~~~~~~~~~~~~~
ceste.cpp:61:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         int u,v,t,c; std::scanf("%d %d %d %d",&u,&v,&t,&c);
      |                      ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 340 KB Output is correct
2 Correct 61 ms 436 KB Output is correct
3 Correct 18 ms 436 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 348 KB Output is correct
2 Correct 8 ms 488 KB Output is correct
3 Correct 21 ms 472 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 480 KB Output is correct
2 Correct 77 ms 472 KB Output is correct
3 Correct 118 ms 596 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 472 KB Output is correct
2 Correct 178 ms 488 KB Output is correct
3 Correct 10 ms 500 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 476 KB Output is correct
2 Correct 81 ms 492 KB Output is correct
3 Correct 100 ms 492 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 484 KB Output is correct
2 Correct 89 ms 484 KB Output is correct
3 Correct 97 ms 492 KB Output is correct