oj.uz

Submission #629826

# Submission time Handle Problem Language Result Execution time Memory
629826 2022-08-15T08:18:42 Z colazcy Ceste (COCI17_ceste) C++17
96 / 160
 2500 ms 644 KB 
#include <cstdio>
#include <cassert>
#include <vector>
#include <utility>
#include <queue>
#define let const auto
#define rep(name,beg,end) for(auto name = beg,name##_end = end;name <= name##_end;name++)
#define per(name,beg,end) for(auto name = beg,name##_end = end;name >= name##_end;name--)
#define repn(lim) for(auto NOW = 1,END = lim;NOW <= END;NOW++)
#define debug(...) std::fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ll = long long;
using i128 = __int128_t;
constexpr int maxn = 2e3 + 100;

struct Vector{
    ll x,y;
    Vector operator + (const Vector t)const{return Vector{x + t.x,y + t.y};}
    Vector operator - (const Vector t)const{return Vector{x - t.x,y - t.y};}
    i128 operator * (const Vector t)const{return i128(x) * t.y - i128(y) * t.x;}
};
using Point = Vector;
int n,m;
struct Edge{
    int u,v;
    Vector w;
}edges[maxn];
namespace dij{
    std::vector<std::pair<int,std::pair<ll,Vector>>> G[maxn];
    void addedge(const int u,const int v,const std::pair<ll,Vector> w){
        G[u].emplace_back(v,w);
        G[v].emplace_back(u,w);
    }
    void clear(){
        rep(i,1,n)G[i].clear();
    }
    struct Node{
        int u;
        ll h;
        bool operator < (const Node t)const{
            return h > t.h;
        }
    };
    std::priority_queue<Node> q;
    bool vis[maxn];
    ll dis[maxn];
    Vector vec[maxn];
    void dij(const int tag){
        std::fill_n(vis + 1,n,false);
        std::fill_n(dis + 1,n,0x3f3f3f3f3f3f3f3f);
        while(!q.empty())q.pop();
        q.push(Node{1,0});
        dis[1] = 0;
        while(!q.empty()){
            let u = q.top().u; q.pop();
            if(vis[u])continue;
            if(u == tag)return;
            for(let &pir : G[u]){
                let v = pir.first;
                let w = pir.second.first;
                let t = pir.second.second;
                if(dis[u] + w < dis[v]){
                    dis[v] = dis[u] + w;
                    vec[v] = vec[u] + t;
                    q.push(Node{v,dis[v]});
                }
            }
        }
    }
}



ll ans;
void solve(const int tag,const Point a,const Point b){
    dij::clear();
    rep(i,1,m){
        let x = edges[i].w.x,y = edges[i].w.y;
        ll t = (b.x - a.x) * y + (a.y - b.y) * x;
        dij::addedge(edges[i].u,edges[i].v,{t,edges[i].w});
    }
    dij::dij(tag);

    let p = dij::vec[tag];
    ans = std::min(ans,p.x * p.y);
	if((b - a) * (p - a) >= 0)return;
    
    solve(tag,a,p);
    solve(tag,p,b);
}


int main(){
#ifndef ONLINE_JUDGE
    // std::freopen("fufu.in","r",stdin);
    // std::freopen("fufu.out","w",stdout);
#endif
    std::scanf("%d %d",&n,&m);
    rep(i,1,m)
        std::scanf("%d %d %lld %lld",&edges[i].u,&edges[i].v,&edges[i].w.x,&edges[i].w.y);
    rep(i,2,n){
        ans = 0x7fffffffffffffff;
        
        dij::clear();
        rep(i,1,m)dij::addedge(edges[i].u,edges[i].v,{edges[i].w.x,edges[i].w});
        dij::dij(i);
        
        if(dij::dis[i] == 0x3f3f3f3f3f3f3f3f){
            std::puts("-1");
            continue;
        }

        const Point a = dij::vec[i];
        ans = std::min(ans,dij::vec[i].x * dij::vec[i].y);

        dij::clear();
        rep(i,1,m)dij::addedge(edges[i].u,edges[i].v,{edges[i].w.y,edges[i].w});
        dij::dij(i);
        const Point b = dij::vec[i];
        ans = std::min(ans,dij::vec[i].x * dij::vec[i].y);

        solve(i,a,b);
        std::printf("%lld\n",ans);
    }
    return 0;
}

Compilation message

ceste.cpp: In function 'int main()':
ceste.cpp:98:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     std::scanf("%d %d",&n,&m);
      |     ~~~~~~~~~~^~~~~~~~~~~~~~~
ceste.cpp:100:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         std::scanf("%d %d %lld %lld",&edges[i].u,&edges[i].v,&edges[i].w.x,&edges[i].w.y);
      |         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 364 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 10 ms 360 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 524 KB Output is correct
2 Correct 189 ms 468 KB Output is correct
3 Correct 37 ms 468 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 412 KB Output is correct
2 Correct 281 ms 420 KB Output is correct
3 Correct 192 ms 644 KB Output is correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2565 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2555 ms 624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2563 ms 600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2571 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -