Submission #525632

#	Time	Username	Problem	Language	Result	Execution time	Memory
525632		somo	Travelling Merchant (CCO21_day2problem1)	C++14	25 / 25	526 ms	96832 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define F first
#define S second
using namespace std;

const int N = 200005;

ll n;
ll m;
ll in[N][4], out[N];
unordered_set<ll>f[N],b[N];
bool vis[N];
queue<ll>q;
priority_queue<pii>pq;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    memset(vis,false,sizeof(vis));
    cin >> n >> m;
    for(ll i=1;i<=m;i++){
        ll x,y,z,w;
        cin >> x >> y >> z >> w;
        in[i][0] = x;
        in[i][1] = y;
        in[i][2] = z;
        in[i][3] = w;
        f[x].insert(i);
        b[y].insert(i);
    }
    for(ll i=1;i<=n;i++){
        if(f[i].size() == 0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        out[cur] = -1;
        for(auto &i : b[cur]){
            if(vis[i]) continue;
            vis[i] = 1;
            f[in[i][0]].erase(f[in[i][0]].find(i));
            if(f[in[i][0]].size() == 0) q.push(in[i][0]);
        }
    }
    for(ll i=1;i<=m;i++){
        if(!vis[i]){
            pq.push({in[i][2] , i});
        }
    }
    while(!pq.empty()){
        pii cur = pq.top();
        pq.pop();
        if(vis[cur.S]) continue;
        vis[cur.S] = 1;
        f[in[cur.S][0]].erase(f[in[cur.S][0]].find(cur.S));
        b[in[cur.S][1]].erase(b[in[cur.S][1]].find(cur.S));
        if(f[in[cur.S][0]].empty()){
            for(auto &i : b[in[cur.S][0]]){
                if(!vis[i]){
                    if(cur.F - in[i][3] > in[i][2]) pq.push({cur.F-in[i][3],i});
                }
            }
            out[in[cur.S][0]] = cur.F;
        }
    }
    for(ll i=1;i<n;i++) cout << out[i] << ' ';
    cout << out[n] << endl;
}

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