oj.uz

Submission #28672

# Submission time Handle Problem Language Result Execution time Memory
28672 2017-07-16T08:35:15 Z 슈퍼스타 tlwpdus(#1124, tlwpdus) Alternative Mart (FXCUP2_mart) C++11
0 / 1
 4666 ms 153480 KB 
#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<int> what[50010];
vector<pii> gd[50010];

int msv = 13;

void dijk() {
	int i, j;
	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;

	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 (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:22:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
mart.cpp: In function 'int main()':
mart.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0;j<gd[s].size();j++) {
                 ^
mart.cpp:65: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:68:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a); --a;
                 ^
mart.cpp:73: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:81: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:84: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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 40944 KB Output is correct
2 Correct 6 ms 40944 KB Output is correct
3 Correct 3 ms 40944 KB Output is correct
4 Correct 6 ms 40944 KB Output is correct
5 Correct 0 ms 41076 KB Output is correct
6 Correct 3 ms 40944 KB Output is correct
7 Correct 6 ms 41476 KB Output is correct
8 Correct 13 ms 41472 KB Output is correct
9 Correct 103 ms 45576 KB Output is correct
10 Correct 36 ms 41604 KB Output is correct
11 Correct 119 ms 46092 KB Output is correct
12 Correct 113 ms 46092 KB Output is correct
13 Correct 3393 ms 113084 KB Output is correct
14 Correct 4053 ms 153480 KB Output is correct
15 Correct 176 ms 47544 KB Output is correct
16 Correct 149 ms 47148 KB Output is correct
17 Correct 1809 ms 82116 KB Output is correct
18 Correct 1246 ms 81600 KB Output is correct
19 Correct 2063 ms 91808 KB Output is correct
20 Correct 2029 ms 90972 KB Output is correct
21 Correct 2056 ms 92172 KB Output is correct
22 Correct 2323 ms 91108 KB Output is correct
23 Correct 2423 ms 97912 KB Output is correct
24 Correct 2583 ms 95528 KB Output is correct
25 Correct 2279 ms 99628 KB Output is correct
26 Correct 2496 ms 97508 KB Output is correct
27 Correct 166 ms 47844 KB Output is correct
28 Correct 156 ms 47548 KB Output is correct
29 Correct 2229 ms 83180 KB Output is correct
30 Correct 1989 ms 82252 KB Output is correct
31 Correct 2496 ms 103320 KB Output is correct
32 Correct 2276 ms 95616 KB Output is correct
33 Correct 2309 ms 101208 KB Output is correct
34 Correct 3539 ms 125736 KB Output is correct
35 Correct 3129 ms 113716 KB Output is correct
36 Correct 3639 ms 123616 KB Output is correct
37 Correct 3403 ms 132368 KB Output is correct
38 Correct 3813 ms 128164 KB Output is correct
39 Correct 213 ms 48332 KB Output is correct
40 Correct 236 ms 48336 KB Output is correct
41 Correct 2456 ms 84576 KB Output is correct
42 Correct 2706 ms 84580 KB Output is correct
43 Correct 4003 ms 127148 KB Output is correct
44 Correct 4093 ms 129656 KB Output is correct
45 Correct 4062 ms 142100 KB Output is correct
46 Correct 4089 ms 140108 KB Output is correct
47 Correct 3173 ms 148052 KB Output is correct
48 Correct 4426 ms 149368 KB Output is correct
49 Correct 4379 ms 149772 KB Output is correct
50 Correct 4666 ms 151480 KB Output is correct
51 Incorrect 4459 ms 153204 KB Output isn't correct
52 Halted 0 ms 0 KB -