Submission #1102436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102436		Thanhs	Travelling Merchant (CCO21_day2problem1)	C++17	25 / 25	115 ms	23020 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))

mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 2e5 + 5;

struct Edge
{
    int u, v, r, p;
    bool operator<(const Edge& o)
    {
        return r < o.r;
    }
}E[NM];

vector<int> g[NM];
int n, m, deg[NM], ans[NM];
bool ok[NM];

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> E[i].u >> E[i].v >> E[i].r >> E[i].p;
    sort(E + 1, E + 1 + m);
    for (int i = 1; i <= m; i++)
    {
        g[E[i].v].push_back(i);
        deg[E[i].u]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        ans[i] = -2;
        if (!deg[i])
            q.push(i);
    }
    while (q.size())
    {
        int u = q.front();
        q.pop();
        ans[u] = -1;
        for (int v : g[u])
        {
            deg[E[v].u]--;
            ok[v] = 1;
            if (!deg[E[v].u])
                q.push(E[v].u);
        }
    }
    for (int i = m; i >= 1; i--)
        if (!ok[i])
        {
            ok[i] = 1;
            deg[E[i].u]--;
            if (ans[E[i].u] == -2)
                ans[E[i].u] = E[i].r;
            else
                setmin(ans[E[i].u], E[i].r);
            if (!deg[E[i].u])
            {
                q.push(E[i].u);
                while (q.size())
                {
                    int u = q.front();
                    q.pop();
                    for (int v : g[u])
                        if (!ok[v])
                        {
                            if (ans[E[v].u] == -2)
                                ans[E[v].u] = max(ans[u] - E[v].p, E[v].r);
                            else
                                setmin(ans[E[v].u], max(ans[u] - E[v].p, E[v].r));
                            deg[E[v].u]--;
                            ok[v] = 1;
                            if (!deg[E[v].u])
                                q.push(E[v].u);
                        }
                }
            }
        }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    int tc = 1; 
    // cin >> tc;
    while (tc--)
        solve();
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16