Submission #697881

#	Time	Username	Problem	Language	Result	Execution time	Memory
697881		azberjibiou	Travelling Merchant (CCO21_day2problem1)	C++17	25 / 25	477 ms	73680 KiB

Main

#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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16