oj.uz

Submission #28625

# Submission time Handle Problem Language Result Execution time Memory
28625 2017-07-16T08:10:59 Z 슈퍼스타 tlwpdus(#1124, tlwpdus) Alternative Mart (FXCUP2_mart) C++11
0 / 1
 4843 ms 144360 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[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

# Verdict Execution time Memory 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 -