/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define int long long
#define isz(x) (int)x.size()
using namespace std;
template<class T>
struct graph{
using Weight_t = T;
struct Edge_t{
int from, to;
T cost;
};
int n;
vector<Edge_t> edge;
vector<vector<int>> adj;
function<bool(int)> ignore;
graph(int n = 1): n(n), adj(n){
assert(n >= 1);
}
graph(const vector<vector<int>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
assert(n >= 1);
if(undirected){
for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v);
}
else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v);
}
graph(const vector<vector<pair<int, T>>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
assert(n >= 1);
if(undirected){
for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w);
}
else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w);
}
graph(int n, vector<array<int, 2>> &edge, bool undirected = true): n(n), adj(n){
assert(n >= 1);
for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v);
}
graph(int n, vector<tuple<int, int, T>> &edge, bool undirected = true): n(n), adj(n){
assert(n >= 1);
for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w);
}
int add_vertex(){
adj.emplace_back();
return n ++;
}
int operator()(int u, int id) const{
#ifdef LOCAL
assert(0 <= id && id < (int)edge.size());
assert(edge[id].from == u || edge[id].to == u);
#endif
return u ^ edge[id].from ^ edge[id].to;
}
int link(int u, int v, T w = {}){ // insert an undirected edge
int id = (int)edge.size();
adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w});
return id;
}
int orient(int u, int v, T w = {}){ // insert a directed edge
int id = (int)edge.size();
adj[u].push_back(id), edge.push_back({u, v, w});
return id;
}
vector<int> neighbor(int u, int exclude = -1) const{
vector<int> res;
for(auto id: adj[u]){
if(id == exclude || ignore && ignore(id)) continue;
res.push_back(operator()(u, id));
}
return res;
}
void clear(){
for(auto [u, v, w]: edge){
adj[u].clear();
adj[v].clear();
}
edge.clear();
ignore = {};
}
graph transpose() const{ // the transpose of the directed graph
graph res(n);
for(auto id = 0; id < (int)edge.size(); ++ id){
if(ignore && ignore(id)) continue;
res.orient(edge[id].to, edge[id].from, edge[id].cost);
}
return res;
}
int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule)
return (int)adj[u].size();
}
// The adjacency list is sorted for each vertex.
vector<vector<int>> get_adjacency_list() const{
vector<vector<int>> res(n);
for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){
if(ignore && ignore(id)) continue;
res[(*this)(u, id)].push_back(u);
}
return res;
}
void set_ignoration_rule(const function<bool(int)> &f){
ignore = f;
}
void reset_ignoration_rule(){
ignore = nullptr;
}
friend ostream &operator<<(ostream &out, const graph &g){
for(auto id = 0; id < (int)g.edge.size(); ++ id){
if(g.ignore && g.ignore(id)) continue;
auto &e = g.edge[id];
out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n";
}
return out;
}
};
const int inf = 1e18;
const int lim = 1e10;
void solve() {
int n, m;
cin >> n >> m;
vector<int> outdeg(n);
graph<pair<int, int>> g(n), rg(n);
for (int i = 0; i < m; ++i) {
int u, v, r, p;
cin >> u >> v >> r >> p;
--u, --v;
g.orient(u, v, {r, p});
rg.orient(v, u, {r, p});
++outdeg[u];
}
vector<int> vec;
vector<int> vis_edge(m);
for (int i = 0; i < n; ++i) {
if (outdeg[i] == 0) {
vec.emplace_back(i);
}
}
while (not vec.empty()) {
int u = vec.back();
vec.pop_back();
for (auto id : rg.adj[u]) {
auto v = rg(u, id);
vis_edge[id] = true;
if (--outdeg[v] == 0) {
vec.emplace_back(v);
}
}
}
vector<int> needed(n, -1);
priority_queue<pair<int, int>> pq;
for (int i = 0; i < m; ++i) if (not vis_edge[i]) {
pq.emplace(g.edge[i].cost.first, i);
}
while (not pq.empty()) {
auto [r, id] = pq.top();
pq.pop();
if (vis_edge[id]) {
continue;
}
vis_edge[id] = true;
auto u = g.edge[id].from;
needed[u] = r;
if (--outdeg[u] == 0) {
for (auto id : rg.adj[u]) {
pq.emplace(needed[u] - g.edge[id].cost.second, id);
}
}
}
for (int i = 0; i < m; ++i) {
cout << needed[i] << " \n"[i + 1 == m];
}
}
signed main() {
#ifndef CDuongg
if (fopen(taskname".inp", "r"))
assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
auto start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; //cin >> t;
while(t--) solve();
#ifdef CDuongg
auto end = chrono::high_resolution_clock::now();
cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
848 KB |
Output is correct |
| 2 |
Correct |
2 ms |
876 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
145 ms |
41592 KB |
Output is correct |
| 2 |
Correct |
154 ms |
46476 KB |
Output is correct |
| 3 |
Incorrect |
124 ms |
36128 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
848 KB |
Output is correct |
| 2 |
Correct |
2 ms |
876 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
