oj.uz

Submission #525631

# Submission time Handle Problem Language Result Execution time Memory
525631 2022-02-12T08:15:54 Z somo Travelling Merchant (CCO21_day2problem1) C++14
0 / 25
 391 ms 144212 KB 
#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].empty()){
            q.push(i);
        }
    }
    while(q.size()){
        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]].empty()) q.push(in[i][0]);
        }
    }
    for(ll i=1;i<=m;i++){
        if(!vis[i]){
            pq.push({in[i][2] , i});
        }
    }
    while(pq.size()){
        pii cur = pq.top();
        q.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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 46244 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 391 ms 144212 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 46244 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -