oj.uz

Submission #74346

# Submission time Handle Problem Language Result Execution time Memory
74346 2018-08-31T10:55:36 Z khsoo01 Alternative Mart (FXCUP2_mart) C++11
1 / 1
 546 ms 143416 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
const int inf = 1e9;
 
int n, m, k, q, c[50005], vis[50005], ts;
pii d[50005][12];
 
vector<pii> adj[50005];
priority_queue<pair<pii,int> > pq;
 
bool upd (int I, pii V) {
	for(int i=0;i<11;i++) {
		if(d[I][i] < V) {
			pii T = d[I][i];
			d[I][i] = V;
			for(int j=i+1;j<11;j++) {
				if(T.Y == V.Y) return true;
				swap(d[I][j], T);
			}
			return true;
		}
		if(d[I][i].Y == V.Y) return false;
	}
	return false;
}
 
int main()
{
	scanf("%d%d%d%d",&n,&m,&k,&q);
	for(int i=1;i<=n;i++) {
		for(int j=0;j<11;j++) d[i][j] = pii(-inf, 1);
	}
	for(int i=1;i<=k;i++) {
		int T;
		scanf("%d",&T);
		upd(T, pii(0, -T));
		pq.push({pii(0, -T), T});
	}
	for(int i=1;i<=m;i++) {
		int A, B, C;
		scanf("%d%d%d",&A,&B,&C);
		adj[A].push_back({B, C});
		adj[B].push_back({A, C});
	}
	while(!pq.empty()) {
		pii V; int I; tie(V, I) = pq.top(); pq.pop();
		if(c[I] == 11 || d[I][c[I]] != V) continue;
		c[I]++;
		for(auto &T : adj[I]) {
			int A, B; tie(A, B) = T;
			pii X = pii(V.X-B, V.Y);
			if(upd(A, X)) pq.push({X, A});
		}
	}
	while(q--) {
		int A, M; ts++;
		scanf("%d%d",&A,&M);
		for(int i=0;i<M;i++) {
			int T;
			scanf("%d",&T);
			vis[T] = ts;
		}
		for(int i=0;i<11;i++) {
			if(vis[-d[A][i].Y] == ts) continue;
			printf("%d %d\n",-d[A][i].Y,-d[A][i].X);
			break;
		}
	}
}

Compilation message

mart.cpp: In function 'int main()':
mart.cpp:32:7: 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:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&T);
   ~~~~~^~~~~~~~~
mart.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&A,&B,&C);
   ~~~~~^~~~~~~~~~~~~~~~~~~
mart.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&M);
   ~~~~~^~~~~~~~~~~~~~
mart.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&T);
    ~~~~~^~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB Output is correct
2 Correct 3 ms 1664 KB Output is correct
3 Correct 3 ms 1664 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 4 ms 1664 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 5 ms 1744 KB Output is correct
8 Correct 5 ms 1744 KB Output is correct
9 Correct 19 ms 2676 KB Output is correct
10 Correct 18 ms 2788 KB Output is correct
11 Correct 26 ms 3224 KB Output is correct
12 Correct 22 ms 3224 KB Output is correct
13 Correct 163 ms 9696 KB Output is correct
14 Correct 156 ms 11172 KB Output is correct
15 Correct 77 ms 13896 KB Output is correct
16 Correct 76 ms 14864 KB Output is correct
17 Correct 322 ms 18020 KB Output is correct
18 Correct 222 ms 19664 KB Output is correct
19 Correct 340 ms 23632 KB Output is correct
20 Correct 252 ms 25044 KB Output is correct
21 Correct 349 ms 28936 KB Output is correct
22 Correct 286 ms 30296 KB Output is correct
23 Correct 391 ms 34932 KB Output is correct
24 Correct 431 ms 36596 KB Output is correct
25 Correct 391 ms 40796 KB Output is correct
26 Correct 361 ms 42652 KB Output is correct
27 Correct 93 ms 43712 KB Output is correct
28 Correct 85 ms 44712 KB Output is correct
29 Correct 394 ms 48916 KB Output is correct
30 Correct 344 ms 50392 KB Output is correct
31 Correct 425 ms 54812 KB Output is correct
32 Correct 363 ms 55928 KB Output is correct
33 Correct 390 ms 59872 KB Output is correct
34 Correct 464 ms 63876 KB Output is correct
35 Correct 409 ms 66420 KB Output is correct
36 Correct 449 ms 69588 KB Output is correct
37 Correct 478 ms 74568 KB Output is correct
38 Correct 457 ms 76480 KB Output is correct
39 Correct 110 ms 76480 KB Output is correct
40 Correct 111 ms 77616 KB Output is correct
41 Correct 480 ms 82544 KB Output is correct
42 Correct 455 ms 85152 KB Output is correct
43 Correct 528 ms 89624 KB Output is correct
44 Correct 526 ms 92388 KB Output is correct
45 Correct 546 ms 97212 KB Output is correct
46 Correct 498 ms 100196 KB Output is correct
47 Correct 450 ms 104316 KB Output is correct
48 Correct 526 ms 108712 KB Output is correct
49 Correct 443 ms 112428 KB Output is correct
50 Correct 495 ms 117036 KB Output is correct
51 Correct 439 ms 121640 KB Output is correct
52 Correct 496 ms 126696 KB Output is correct
53 Correct 226 ms 126696 KB Output is correct
54 Correct 501 ms 133308 KB Output is correct
55 Correct 507 ms 138172 KB Output is correct
56 Correct 535 ms 143416 KB Output is correct
57 Correct 147 ms 143416 KB Output is correct