답안 #28625 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
28625	2017-07-16T08:10:59 Z	슈퍼스타 tlwpdus(#1124, tlwpdus)	Alternative Mart (FXCUP2_mart)	C++11	0 / 1	4843 ms	144360 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[2200000];
int p;
int dis[2200000];
int cnt[50010];
vector<int> what[50010];
vector<pii> gd[50010];

int msv = 12;

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

	for (i=0;i<2200000;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++) {
		what[rin[i].first].push_back(rin[i].second);
	}

	for (i=0;i<n;i++) {
		sort(what[i].begin(),what[i].end());
		what[i].erase(unique(what[i].begin(),what[i].end()),what[i].end());
		for (int j=0;j<what[i].size();j++) {
			gd[i].push_back(pii(dis[fin[pii(i,what[i][j])]],what[i][j]));
		}
		sort(gd[i].begin(),gd[i].end());
	}
}

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

	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();
	for (i=0;i<q;i++) {
		int s, x;
		que.reserve(12);
		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 (int 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;
			}
		}
		for (int j=0;j<x;j++) {
			qchk[que[j]] = 0;
		}
		que.clear();
	}

    return 0;
}

Compilation message

mart.cpp: In function 'void dijk()':
mart.cpp:64:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0;j<what[i].size();j++) {
                 ^
mart.cpp:22:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
mart.cpp: In function 'int main()':
mart.cpp:99:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0;j<gd[s].size();j++) {
                 ^
mart.cpp:76: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:79:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a); --a;
                 ^
mart.cpp:84: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:92: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:95: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	0 ms	31572 KB	Output is correct
2	Correct	3 ms	31572 KB	Output is correct
3	Correct	6 ms	31572 KB	Output is correct
4	Correct	3 ms	31572 KB	Output is correct
5	Correct	0 ms	31704 KB	Output is correct
6	Correct	3 ms	31704 KB	Output is correct
7	Correct	6 ms	32108 KB	Output is correct
8	Correct	16 ms	32100 KB	Output is correct
9	Correct	156 ms	36468 KB	Output is correct
10	Correct	49 ms	32232 KB	Output is correct
11	Correct	133 ms	36852 KB	Output is correct
12	Correct	136 ms	36720 KB	Output is correct
13	Correct	3343 ms	105032 KB	Output is correct
14	Correct	4179 ms	143184 KB	Output is correct
15	Correct	186 ms	39756 KB	Output is correct
16	Correct	179 ms	39360 KB	Output is correct
17	Correct	1909 ms	76572 KB	Output is correct
18	Correct	1376 ms	75792 KB	Output is correct
19	Correct	2163 ms	83228 KB	Output is correct
20	Correct	2243 ms	82260 KB	Output is correct
21	Correct	2243 ms	83592 KB	Output is correct
22	Correct	2409 ms	82396 KB	Output is correct
23	Correct	1849 ms	89464 KB	Output is correct
24	Correct	2189 ms	86552 KB	Output is correct
25	Correct	1929 ms	91180 KB	Output is correct
26	Correct	2106 ms	88268 KB	Output is correct
27	Correct	139 ms	40056 KB	Output is correct
28	Correct	133 ms	39760 KB	Output is correct
29	Correct	2459 ms	77504 KB	Output is correct
30	Correct	1583 ms	76576 KB	Output is correct
31	Correct	2526 ms	94476 KB	Output is correct
32	Correct	2093 ms	86376 KB	Output is correct
33	Correct	2633 ms	92364 KB	Output is correct
34	Correct	3863 ms	116232 KB	Output is correct
35	Correct	2829 ms	105136 KB	Output is correct
36	Correct	3849 ms	114244 KB	Output is correct
37	Correct	3189 ms	123656 KB	Output is correct
38	Correct	3156 ms	118924 KB	Output is correct
39	Correct	166 ms	40544 KB	Output is correct
40	Correct	293 ms	40416 KB	Output is correct
41	Correct	2229 ms	78900 KB	Output is correct
42	Correct	2166 ms	79036 KB	Output is correct
43	Correct	2846 ms	118436 KB	Output is correct
44	Correct	4493 ms	120812 KB	Output is correct
45	Correct	4369 ms	128896 KB	Output is correct
46	Correct	4789 ms	130472 KB	Output is correct
47	Correct	4503 ms	139208 KB	Output is correct
48	Correct	4699 ms	139996 KB	Output is correct
49	Correct	4416 ms	141060 KB	Output is correct
50	Correct	4843 ms	142240 KB	Output is correct
51	Incorrect	4506 ms	144360 KB	Output isn't correct
52	Halted	0 ms	0 KB	-

답안 #28625

Compilation message

Subtask #1 0 / 1.0

Subtask #1
0 / 1.0