Submission #629823

#	Time	Username	Problem	Language	Result	Execution time	Memory
629823		colazcy	Ceste (COCI17_ceste)	C++17	96 / 160	2595 ms	664 KiB

ceste

#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 spfa{
    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){
        assert(w.first >= 0);
        G[u].emplace_back(v,w);
        G[v].emplace_back(u,w);
    }
    void clear(){
        rep(i,1,n)G[i].clear();
    }
    std::queue<int> q;
    bool inq[maxn];
    ll dis[maxn];
    Vector vec[maxn];
    bool spfa(const int tag){
        std::fill_n(inq + 1,n,false);
        std::fill_n(dis + 1,n,0x3f3f3f3f3f3f3f3f);
        while(!q.empty())q.pop();
        q.push(1);
        dis[1] = 0; inq[1] = 1;
        while(!q.empty()){
            let u = q.front(); q.pop(); inq[u] = 0;
            if(dis[u] < 0)return false;
            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;
                    if(!inq[v])q.push(v),inq[v] = 1;
                }
            }
        }
        return true;
    }
}



ll ans;
void solve(const int tag,const Point a,const Point b){
    spfa::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;
        spfa::addedge(edges[i].u,edges[i].v,{t,edges[i].w});
    }
    
    if(!spfa::spfa(tag))return;

    let p = spfa::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;
        
        spfa::clear();
        rep(i,1,m)spfa::addedge(edges[i].u,edges[i].v,{edges[i].w.x,edges[i].w});
        spfa::spfa(i);
        
        if(spfa::dis[i] == 0x3f3f3f3f3f3f3f3f){
            std::puts("-1");
            continue;
        }

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

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

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

Compilation message (stderr)

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

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16