Submission #629802

#	Time	Username	Problem	Language	Result	Execution time	Memory
629802		colazcy	Ceste (COCI17_ceste)	C++17	0 / 160	1 ms	340 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.x};}
    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(u == tag)return;
            if(vis[u])continue;
            vis[u] = 1;
            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)dij::addedge(edges[i].u,edges[i].v,{edges[i].w.x * (b.y - a.y) + edges[i].w.y * (a.x - b.x),edges[i].w});
    dij::dij(tag);

    let p = dij::vec[tag];
    ans = std::min(ans,p.x * p.y);
	if(p.x * (b.y - a.y) + p.y * (a.x - b.x) - a.x * b.y + a.y * b.x <= 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 (stderr)

ceste.cpp: In function 'int main()':
ceste.cpp:90:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     std::freopen("fufu.in","r",stdin);
      |     ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
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: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16