Submission #1230713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230713		sleepntsheep	Travelling Merchant (CCO21_day2problem1)	C++20	0 / 25	82 ms	15932 KiB

Main

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 200050, M = 200050;

int n, m,kil[M];

struct A {int a,b,r,p;
	A(int a_=0,int b_=0,int r_=0,int p_=0){a=a_,b=b_,r=r_,p=p_;}};



int main() {
	scanf("%d%d",&n,&m);int ii=0;
	vector<A>e(m);
	vector<vector<int>>gg(n);
	vector<int>deg(n),ans(n,-1);
	for(auto&[a,b,r,p]:e){
		scanf("%d%d%d%d",&a,&b,&r,&p),--a,--b;
		gg[b].push_back(ii++);
		++deg[a];
	}

	queue<int>q;
	for(int i=0;i<n;++i){
		if(!deg[i]){
			q.push(i);
		}
	}
	while(q.size()){
		int u=q.front();q.pop();
		for(auto j:gg[u]){
			int v=e[j].a;
			if(!--deg[v]) {
				q.push(v);
				kil[j]=1;
			}
		}
		}

	priority_queue<pair<int,int>>pq;
	for(int i=0;i<m;++i)
		if(!kil[i])pq.push(make_pair(e[i].r,i));

	while(pq.size()){
		auto[ru,j]=pq.top();pq.pop();
		if(kil[j])continue;
		kil[j]=1;
		int a=e[j].a;
		if(!--deg[a]){
			ans[a]=ru;
			for(auto k:gg[a]){
				if(kil[k])continue;
				int b=e[k].a;
				if(e[k].r<ru-e[k].p){
					pq.push(make_pair(ru-e[k].p,k));
				}
			}
		}
	}
	
	
	for(auto x:ans)printf("%d ",x);

	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%d%d",&n,&m);int ii=0;
      |         ~~~~~^~~~~~~~~~~~~~
Main.cpp:23:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |                 scanf("%d%d%d%d",&a,&b,&r,&p),--a,--b;
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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