답안 #28706 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
28706	2017-07-16T08:54:31 Z	슈퍼스타 tlwpdus(#1124, tlwpdus)	Alternative Mart (FXCUP2_mart)	C++11	0 / 1	4809 ms	152308 KB

mart

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

int n, m, k, q;
vector<int> mart;
vector<pii> lis[50010];

map<pii,int> fin;
pii rin[3000000];
int p;
int dis[3000000];
int cnt[50010];
vector<pii> gd[50010];

int msv = 13;

void dijk() {
	int i;
	priority_queue<pii> pq;

	for (i=0;i<3000000;i++) dis[i] = 987654321;
	for (i=0;i<k;i++) {
		fin[pii(mart[i],mart[i])] = p;
		rin[p] = pii(mart[i],mart[i]);
		dis[p] = 0;
		pq.push(pii(0,p));
		p++;
	}

	while(!pq.empty()) {
		pii tmp = pq.top(); pq.pop();
		if (dis[tmp.second]!=-tmp.first||cnt[rin[tmp.second].first]>=msv) continue;
		int here = rin[tmp.second].first, mar = rin[tmp.second].second, d = -tmp.first;
		cnt[here]++;
		for (auto &tmp : lis[here]) {
			int there = tmp.second, w = tmp.first;
			if (cnt[there]>=msv) continue;
			auto it = fin.find(pii(there,mar));
			int curp;
			if (it==fin.end()) {
				curp = p;
				fin[pii(there,mar)] = p;
				rin[p] = pii(there,mar);
				p++;
			}
			else curp = it->second;
			if (dis[curp]<=d+w) continue;
			dis[curp] = d+w;
			pq.push(pii(-d-w,curp));
		}
	}
	for (i=0;i<p;i++) gd[rin[i].first].push_back(pii(dis[i],rin[i].second));
	for (i=0;i<n;i++) sort(gd[i].begin(),gd[i].end());
}

vector<int> que;
bool qchk[50010];
int main() {
	int i, j;

	scanf("%d%d%d%d",&n,&m,&k,&q);
	for (i=0;i<k;i++) {
		int a;
		scanf("%d",&a); --a;
		mart.push_back(a);
	}
	for (i=0;i<m;i++) {
		int a, b, c;
		scanf("%d%d%d",&a,&b,&c); --a; --b;
		lis[a].push_back(pii(c,b));
		lis[b].push_back(pii(c,a));
	}
	dijk();
	que.reserve(12);
	for (i=0;i<q;i++) {
		int s, x;
		scanf("%d%d",&s,&x); --s;
		for (int j=0;j<x;j++) {
			int a;
			scanf("%d",&a); --a;
			que.push_back(a);
			qchk[a] = 1;
		}
		for (j=0;j<gd[s].size();j++) {
			if (!qchk[gd[s][j].second]) {
				printf("%d %d\n",gd[s][j].second+1,gd[s][j].first);
				break;
			}
		}
		if (j==gd[s].size()) {
			while(true) printf("!");
		}
		for (int j=0;j<x;j++) {
			qchk[que[j]] = 0;
		}
		que.clear();
	}

    return 0;
}

Compilation message

mart.cpp: In function 'int main()':
mart.cpp:87:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j=0;j<gd[s].size();j++) {
             ^
mart.cpp:93:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (j==gd[s].size()) {
        ^
mart.cpp:64:31: 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:67:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a); --a;
                 ^
mart.cpp:72:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a,&b,&c); --a; --b;
                           ^
mart.cpp:80:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&s,&x); --s;
                      ^
mart.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a); --a;
                  ^

Subtask #1
0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	39772 KB	Output is correct
2	Correct	6 ms	39772 KB	Output is correct
3	Correct	3 ms	39772 KB	Output is correct
4	Correct	6 ms	39772 KB	Output is correct
5	Correct	6 ms	39904 KB	Output is correct
6	Correct	0 ms	39772 KB	Output is correct
7	Correct	6 ms	40304 KB	Output is correct
8	Correct	3 ms	40300 KB	Output is correct
9	Correct	129 ms	44404 KB	Output is correct
10	Correct	36 ms	40432 KB	Output is correct
11	Correct	106 ms	44920 KB	Output is correct
12	Correct	99 ms	44920 KB	Output is correct
13	Correct	3156 ms	111912 KB	Output is correct
14	Correct	3936 ms	152308 KB	Output is correct
15	Correct	193 ms	46372 KB	Output is correct
16	Correct	159 ms	45976 KB	Output is correct
17	Correct	1856 ms	80944 KB	Output is correct
18	Correct	1246 ms	80428 KB	Output is correct
19	Correct	2156 ms	90636 KB	Output is correct
20	Correct	1976 ms	89800 KB	Output is correct
21	Correct	2106 ms	91000 KB	Output is correct
22	Correct	2303 ms	89936 KB	Output is correct
23	Correct	2586 ms	96740 KB	Output is correct
24	Correct	2736 ms	94356 KB	Output is correct
25	Correct	2383 ms	98456 KB	Output is correct
26	Correct	2639 ms	96336 KB	Output is correct
27	Correct	206 ms	46672 KB	Output is correct
28	Correct	199 ms	46376 KB	Output is correct
29	Correct	2463 ms	82008 KB	Output is correct
30	Correct	2025 ms	81080 KB	Output is correct
31	Correct	2843 ms	102148 KB	Output is correct
32	Correct	2599 ms	94444 KB	Output is correct
33	Correct	2479 ms	100036 KB	Output is correct
34	Correct	3893 ms	124564 KB	Output is correct
35	Correct	3289 ms	112544 KB	Output is correct
36	Correct	3566 ms	122444 KB	Output is correct
37	Correct	3669 ms	131196 KB	Output is correct
38	Correct	3699 ms	126992 KB	Output is correct
39	Correct	226 ms	47160 KB	Output is correct
40	Correct	233 ms	47164 KB	Output is correct
41	Correct	2649 ms	83404 KB	Output is correct
42	Correct	2639 ms	83408 KB	Output is correct
43	Correct	4046 ms	125976 KB	Output is correct
44	Correct	4223 ms	128484 KB	Output is correct
45	Correct	4136 ms	140928 KB	Output is correct
46	Correct	4623 ms	138936 KB	Output is correct
47	Correct	4446 ms	146880 KB	Output is correct
48	Correct	4809 ms	148196 KB	Output is correct
49	Correct	4386 ms	148600 KB	Output is correct
50	Correct	4659 ms	150308 KB	Output is correct
51	Incorrect	4503 ms	152032 KB	Output isn't correct
52	Halted	0 ms	0 KB	-

답안 #28706

Compilation message

Subtask #1 0 / 1.0

Subtask #1
0 / 1.0