Submission #28709

#	Time	Username	Problem	Language	Result	Execution time	Memory
28709		tlwpdus 팬클럽 회장 (#68)	Alternative Mart (FXCUP2_mart)	C++14	0 / 1	5000 ms	40020 KiB

mart

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

struct Dat{
	int s, x, d;
	bool operator<(const Dat &oth) const {
		return (d == oth.d) ? (s > oth.s) : (d > oth.d);
	}
};

const int inf = 1e9;
int n, m, k, q, chk[50010];
set<pii> md[50010];
vector<pii> e[50010];
priority_queue<Dat> pq;

int main(){
	scanf("%d%d%d%d", &n, &m, &k, &q);
	for(int i = 1, x; i <= k; i++){
		scanf("%d", &x);
		md[x].insert(pii(0, x));
		pq.push({x, x, 0});
	}
	for(int x, y, c; m--; ){
		scanf("%d%d%d", &x, &y, &c);
		e[x].push_back({y, c});
		e[y].push_back({x, c});
	}
	while(!pq.empty()){
		Dat c = pq.top(); pq.pop();
		int fl = 1;
		for(auto &i : md[c.x]){
			if(i.second == c.s && i.first < c.d){
				fl = 0;
				break;
			}
		}
		if(!fl) continue;
		for(auto &i : e[c.x]){
			int nx, nd; tie(nx, nd) = i;
			nd += c.d;
			int fl = 1;
			for(auto &i : md[nx]){
				if(i.second == c.s && i.first <= nd){ fl = 0; break; }
			}
			if(!fl) continue;
			for(auto &i : md[nx]){
				if(i.second == c.s){
					md[nx].erase(i);
					break;
				}
			}
			md[nx].insert(pii(nd, c.s));
			while(md[nx].size() > 11){
				auto t = md[nx].end();
				t--;
				md[nx].erase(t);
			}
			auto t = md[nx].end(); t--;
			if(md[nx].find(pii(nd, c.s)) != md[nx].end()) pq.push({c.s, nx, nd});
		}
	}
	for(int i = 1, x, c; i <= q; i++){
		scanf("%d%d", &x, &c);
		for(int y; c--; ){
			scanf("%d", &y);
			chk[y] = i;
		}
		for(auto &j : md[x]){
			if(chk[j.second] == i) continue;
			printf("%d %d\n", j.second, j.first);
			break;
		}
	}
}

Compilation message (stderr)

mart.cpp: In function 'int main()':
mart.cpp:19: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:21:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
                  ^
mart.cpp:26: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, &c);
                        ^
mart.cpp:67:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &y);
                   ^

• Subtask 1: 0 / 1