| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 654924 |
2022-11-02T01:54:38 Z |
jeroenodb |
Ceste (COCI17_ceste) |
C++14 |
|
314 ms |
16968 KB |
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
typedef complex<int> pt;
#define X real()
#define Y imag()
auto cross(pt u, pt v) {return (ll)u.X*v.Y-(ll)u.Y*v.X;}
auto sgn(ll a) {return a==0?0:(a>0?1:-1);}
auto ccw(pt p1, pt p2, pt p3) {auto u = p2-p1, v = p3-p2;return cross(u,v);}
auto in(pt p1, pt p2) {return (ll)p1.X*p2.X+(ll)p1.Y*p2.Y;}
auto norm(pt p) {return (ll)p.X*p.X+(ll)p.Y*p.Y;}
bool comp(const pt& a, const pt& b) { return a.X<b.X or (a.X==b.X and a.Y > b.Y);}
void read(pt& p) {
int a,b; cin >> a >> b;
p = {a,b};
}
struct cmp {
bool operator()(const pt& a, const pt& b)const {
return comp(a,b);
}
};
int main() {
// freopen("ceste.in","r",stdin);
int n,m; cin >> n >> m;
vector<vector<array<int,3>>> adj(n);
for(int i=0;i<m;++i) {
int a,b,t,c; cin >> a >> b >> t >> c;
--a,--b;
adj[a].push_back({b,t,c});
adj[b].push_back({a,t,c});
}
struct Hull {
set<pt,cmp> s;
bool inside(pt p) {
if(s.empty()) return false;
auto it = s.lower_bound(p);
if(it==s.end()) {
--it;
return it->Y <= p.Y;
} else if(it==s.begin()) {
return (*it==p);
}
auto pit = prev(it);
return ccw(*pit,p,*it)<=0;
}
bool corner(pt p) {
return s.count(p);
}
void insert(pt p) {
if(inside(p)) return;
auto [it,b] = s.insert(p);
assert(b);
if(it!=s.begin()) {
auto pit = prev(it);
while(pit!=s.begin()) {
auto ppit = prev(pit);
if(ccw(*ppit,*pit,p)<=0) {
s.erase(pit);
pit = ppit;
} else break;
}
}
if(next(it)!=s.end()) {
auto pit = next(it);
while(next(pit)!=s.end()) {
auto ppit = next(pit);
if(ccw(p,*pit,*ppit)<=0) {
s.erase(pit);
pit = ppit;
} else break;
}
if(pit->Y>=p.Y) s.erase(pit);
}
}
};
vector<Hull> hs(n);
struct el {
int t,c;
int at;
ll cost() const {
return ll(t)*c;
}
bool operator<(const el& o) const {
return cost()>o.cost();
}
};
priority_queue<el> pq;
auto process = [&](int at, int t,int c) {
if(!hs[at].inside({t,c})) {
hs[at].insert({t,c});
pq.push({t,c,at});
}
};
process(0,0,0);
vector<ll> ans(n,1e18);
while(!pq.empty()) {
auto e = pq.top(); pq.pop();
ans[e.at] = min(ans[e.at],e.cost());
if(hs[e.at].corner({e.t,e.c})) {
for(auto [to,t,c] : adj[e.at]) {
process(to,e.t+t,e.c+c);
}
}
}
for(auto& i : ans) {
if(i==ll(1e18)) i=-1;
}
for(int i=1;i<n;++i) cout << ans[i] << '\n';
}
Compilation message
ceste.cpp: In member function 'void main()::Hull::insert(pt)':
ceste.cpp:59:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
59 | auto [it,b] = s.insert(p);
| ^
ceste.cpp: In function 'int main()':
ceste.cpp:110:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
110 | for(auto [to,t,c] : adj[e.at]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
568 KB |
Output is correct |
| 2 |
Correct |
3 ms |
440 KB |
Output is correct |
| 3 |
Correct |
3 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
940 KB |
Output is correct |
| 2 |
Correct |
15 ms |
820 KB |
Output is correct |
| 3 |
Correct |
7 ms |
528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
253 ms |
16968 KB |
Output is correct |
| 2 |
Correct |
176 ms |
4436 KB |
Output is correct |
| 3 |
Correct |
4 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1464 KB |
Output is correct |
| 2 |
Correct |
194 ms |
8552 KB |
Output is correct |
| 3 |
Correct |
4 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
2312 KB |
Output is correct |
| 2 |
Correct |
293 ms |
16244 KB |
Output is correct |
| 3 |
Correct |
181 ms |
11536 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
273 ms |
16484 KB |
Output is correct |
| 2 |
Correct |
219 ms |
13216 KB |
Output is correct |
| 3 |
Correct |
314 ms |
16552 KB |
Output is correct |
