Submission #28785

#	Time	Username	Problem	Language	Result	Execution time	Memory
28785		kriii	Alternative Mart (FXCUP2_mart)	C++14	1 / 1	4473 ms	51040 KiB

mart

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
 
struct phase{
	int s,x,c;
	bool operator <(const phase &t) const{return c > t.c;}
};
priority_queue<phase> Q;
map<int, int> dist[50505];
 
vector<pair<int, int> > G[50505];
int N,M,K,q;
 
pair<int, int> mx(map<int, int> &m)
{
	pair<int, int> ret;
	for (auto &p : m){
		ret = max(ret,{p.second,p.first});
	}
	return ret;
}
 
int main()
{
	scanf ("%d %d %d %d",&N,&M,&K,&q);
	for (int i=0;i<K;i++){
		int x; scanf ("%d",&x);
		dist[x][x] = 0;
		Q.push({x,x,0});
	}
 
	for (int i=0;i<M;i++){
		int x,y,c;
		scanf ("%d %d %d",&x,&y,&c);
		G[x].push_back({y,c});
		G[y].push_back({x,c});
	}
 
	while (!Q.empty()){
		int s = Q.top().s, x = Q.top().x, c = Q.top().c; Q.pop();
		if (!dist[x].count(s) || dist[x][s] != c) continue;
		for (auto &p : G[x]){
			int y = p.first;
			int nc = c + p.second;
			if (dist[y].count(s) && dist[y][s] <= nc) continue;
			if (dist[y].size() < 12 || mx(dist[y]) > make_pair(nc,s)){
				dist[y][s] = nc;
				if (dist[y].size() == 12){
					auto p = mx(dist[y]);
					dist[y].erase(p.second);
				}
				Q.push({s,y,nc});
			}
		}
	}
 
	while (q--){
		int x,n;
		set<int> chk;
		scanf ("%d %d",&x,&n); while (n--){
			int t; scanf ("%d",&t); chk.insert(t);
		}
 
		vector<pair<int, int> > u;
		for (auto &p : dist[x]){
			u.push_back({p.second,p.first});
		}
		sort(u.begin(),u.end());
		for (auto &p : u){
			if(!chk.count(p.second)){
				printf ("%d %d\n",p.second,p.first);
				break;
			}
		}
	}
 
	return 0;
}

Compilation message (stderr)

mart.cpp: In function 'int main()':
mart.cpp:30:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d %d %d %d",&N,&M,&K,&q);
                                   ^
mart.cpp:32:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf ("%d",&x);
                         ^
mart.cpp:39:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d %d",&x,&y,&c);
                              ^
mart.cpp:65:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d %d",&x,&n); while (n--){
                        ^
mart.cpp:66:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int t; scanf ("%d",&t); chk.insert(t);
                          ^

• Subtask 1: 1 / 1