/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI acos(-1.0)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x, i) (1 & ((x) >> (i)))
#define MASK(x) (1LL << (x))
#define task "tnc"
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i <= (n); i++)
typedef long long ll;
typedef long double ld;
const ll INF = 1e18;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int mo = 998244353;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using pii = pair<pair<ll, ll>, ll>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, m;
struct Edge
{
int a, b, r, p;
bool operator<(const Edge &x)
{
return r < x.r;
}
} ind[maxn];
vector<int> G[maxn];
int deg[maxn];
int ans[maxn];
bool ok[maxn];
signed main()
{
cin.tie(0), cout.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> ind[i].a >> ind[i].b >> ind[i].r >> ind[i].p;
}
sort(ind + 1, ind + 1 + m);
for (int i = 1; i <= m; i++)
{
G[ind[i].b].pb(i);
deg[ind[i].a]++;
}
queue<int> qu;
for (int i = 1; i <= n; i++)
{
ans[i] = -2;
if (deg[i] == 0)
{
qu.push(i);
}
}
while (qu.size())
{
int u = qu.front();
qu.pop();
ans[u] = -1;
for (auto v : G[u])
{
deg[ind[v].a]--;
ok[v] = 1;
if (deg[ind[v].a] == 0)
{
qu.push(ind[v].a);
}
}
}
for (int i = m; i >= 1; i--)
{
if (ok[i] == 0)
{
deg[ind[i].a]--;
if (ans[ind[i].b] >= 0)
{
if (ans[ind[i].a] == -2)
{
ans[ind[i].a] = max(ans[ind[i].b] - ind[i].p, ind[i].r);
}
else
{
ans[ind[i].a] = min(ans[ind[i].a], max(ans[ind[i].b] - ind[i].p, ind[i].r));
}
}
else
{
if (ans[ind[i].a] == -2)
{
ans[ind[i].a] = ind[i].r;
}
else
{
ans[ind[i].a] = min(ans[ind[i].a], ind[i].r);
}
}
if (deg[ind[i].a] == 0)
{
qu.push(ind[i].a);
while (qu.size())
{
int u = qu.front();
qu.pop();
for (auto v : G[u])
{
deg[ind[v].a]--;
ok[v] = 1;
if (ans[ind[v].a] == -2)
{
ans[ind[v].a] = max(ans[ind[v].b] - ind[v].p, ind[v].r);
}
else
{
ans[ind[v].a] = min(ans[ind[v].a], max(ans[ind[v].b] - ind[v].p, ind[v].r));
}
if (deg[ind[v].a] == 0)
{
qu.push(ind[v].a);
}
}
}
}
}
}
for (int i = 1; i <= n; i++)
{
cout << ans[i] << " ";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
23892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
119 ms |
38400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
23892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
