oj.uz

Submission #697881

# Submission time Handle Problem Language Result Execution time Memory
697881 2023-02-11T09:27:45 Z azberjibiou Travelling Merchant (CCO21_day2problem1) C++17
25 / 25
 477 ms 73680 KB 
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=200005;
struct edge{
    ll s, r, p;
    edge() : s(), r(), p() {}
    edge(ll s, ll r, ll p) : s(s), r(r), p(p) {}
};
struct re{
    ll a, b, r, p;
    re() : a(), b(), r(), p() {}
    re(ll a, ll b, ll r, ll p) : a(a), b(b), r(r), p(p) {}
};
int N, M;
int deg[mxN];
vector <edge> v[mxN], rv[mxN];
vector <re> E;
queue <int> que;
ll ans[mxN];
vector <ll> val[mxN];
multiset <ll> s[mxN];
multiset <pll> cont;
int main()
{
    gibon
    cin >> N >> M;
    for(int i=1;i<=N;i++)   ans[i]=-2;
    for(int i=1;i<=M;i++)
    {
        ll a, b, r, p;
        cin >> a >> b >> r >> p;
        v[a].emplace_back(b, r, p);
        rv[b].emplace_back(a, r, p);
        E.emplace_back(a, b, r, p);
        deg[a]++;
    }
    for(int i=1;i<=N;i++)   if(deg[i]==0)   que.push(i);
    while(que.size())
    {
        int now=que.front();
        que.pop();
        ans[now]=-1;
        for(auto [a, r, p] : rv[now])
        {
            deg[a]--;
            if(deg[a]==0)   que.push(a);
        }
    }
    for(int i=1;i<=N;i++)   v[i].clear(), rv[i].clear();
    for(auto [a, b, r, p] : E)  if(ans[a]!=-1 && ans[b]!=-1)    v[a].emplace_back(b, r, p), rv[b].emplace_back(a, r, p);
    for(int i=1;i<=N;i++)   if(ans[i]!=-1)
    {
        for(auto [a, r, p] : v[i])  s[i].insert(r);
        cont.insert(pll(*s[i].begin(), i));
    }
    /*for(int i=1;i<=N;i++)
    {
        printf("i=%d: ", i);
        for(ll now : s[i])  printf("%lld ", now);
        printf("\n");
    }*/
    while(cont.size())
    {
        auto [nv, now]=*cont.rbegin();
        auto it=cont.end(); it--;
        cont.erase(it);
        ans[now]=nv;
        for(auto [a, r, p] : rv[now])   if(ans[a]==-2)
        {
            cont.erase(pll(*s[a].begin(), a));
            assert(s[a].find(r)!=s[a].end());
            s[a].erase(s[a].find(r));
            s[a].insert(max(ans[now]-p, r));
            cont.insert(pll(*s[a].begin(), a));
        }
    }
    for(int i=1;i<=N;i++)   cout << ans[i] << " ";
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24148 KB Output is correct
2 Correct 13 ms 24008 KB Output is correct
3 Correct 13 ms 24148 KB Output is correct
4 Correct 14 ms 24188 KB Output is correct
5 Correct 13 ms 24148 KB Output is correct
6 Correct 13 ms 24212 KB Output is correct
7 Correct 13 ms 24148 KB Output is correct
8 Correct 13 ms 24220 KB Output is correct
9 Correct 14 ms 24216 KB Output is correct
10 Correct 13 ms 24148 KB Output is correct
11 Correct 13 ms 24172 KB Output is correct
12 Correct 12 ms 24088 KB Output is correct
13 Correct 13 ms 24024 KB Output is correct
14 Correct 13 ms 24320 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 51196 KB Output is correct
2 Correct 216 ms 51040 KB Output is correct
3 Correct 175 ms 56104 KB Output is correct
4 Correct 36 ms 28808 KB Output is correct
5 Correct 346 ms 65528 KB Output is correct
6 Correct 332 ms 65512 KB Output is correct
7 Correct 175 ms 55440 KB Output is correct
8 Correct 462 ms 73648 KB Output is correct
9 Correct 477 ms 69736 KB Output is correct
10 Correct 173 ms 54688 KB Output is correct
11 Correct 332 ms 61492 KB Output is correct
12 Correct 163 ms 53292 KB Output is correct
13 Correct 136 ms 51196 KB Output is correct
14 Correct 427 ms 73600 KB Output is correct
15 Correct 435 ms 73676 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24148 KB Output is correct
2 Correct 13 ms 24008 KB Output is correct
3 Correct 13 ms 24148 KB Output is correct
4 Correct 14 ms 24188 KB Output is correct
5 Correct 13 ms 24148 KB Output is correct
6 Correct 13 ms 24212 KB Output is correct
7 Correct 13 ms 24148 KB Output is correct
8 Correct 13 ms 24220 KB Output is correct
9 Correct 14 ms 24216 KB Output is correct
10 Correct 13 ms 24148 KB Output is correct
11 Correct 13 ms 24172 KB Output is correct
12 Correct 12 ms 24088 KB Output is correct
13 Correct 13 ms 24024 KB Output is correct
14 Correct 13 ms 24320 KB Output is correct
15 Correct 213 ms 51196 KB Output is correct
16 Correct 216 ms 51040 KB Output is correct
17 Correct 175 ms 56104 KB Output is correct
18 Correct 36 ms 28808 KB Output is correct
19 Correct 346 ms 65528 KB Output is correct
20 Correct 332 ms 65512 KB Output is correct
21 Correct 175 ms 55440 KB Output is correct
22 Correct 462 ms 73648 KB Output is correct
23 Correct 477 ms 69736 KB Output is correct
24 Correct 173 ms 54688 KB Output is correct
25 Correct 332 ms 61492 KB Output is correct
26 Correct 163 ms 53292 KB Output is correct
27 Correct 136 ms 51196 KB Output is correct
28 Correct 427 ms 73600 KB Output is correct
29 Correct 435 ms 73676 KB Output is correct
30 Correct 206 ms 51104 KB Output is correct
31 Correct 209 ms 51108 KB Output is correct
32 Correct 157 ms 55116 KB Output is correct
33 Correct 36 ms 28816 KB Output is correct
34 Correct 363 ms 65612 KB Output is correct
35 Correct 338 ms 65596 KB Output is correct
36 Correct 183 ms 55668 KB Output is correct
37 Correct 439 ms 73680 KB Output is correct
38 Correct 461 ms 70700 KB Output is correct
39 Correct 169 ms 54424 KB Output is correct
40 Correct 322 ms 61396 KB Output is correct
41 Correct 152 ms 53308 KB Output is correct
42 Correct 136 ms 51208 KB Output is correct
43 Correct 430 ms 73644 KB Output is correct
44 Correct 419 ms 73644 KB Output is correct
45 Correct 468 ms 73600 KB Output is correct
46 Correct 340 ms 61660 KB Output is correct
47 Correct 331 ms 63024 KB Output is correct
48 Correct 294 ms 63524 KB Output is correct
49 Correct 327 ms 63520 KB Output is correct
50 Correct 12 ms 23764 KB Output is correct