oj.uz

Submission #29074

# Submission time Handle Problem Language Result Execution time Memory
29074 2017-07-18T08:03:54 Z cki86201 Alternative Mart (FXCUP2_mart) C++11
0 / 1
 0 ms 4640 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;
typedef long double ldouble;

int n, m, k, q;
vector <int> mart;
vector <pii> E[50050];
vector <pii> M[50050];

void solve() {
	scanf("%d%d%d%d", &n, &m, &k, &q);
	rep(i, k) {
		int x; scanf("%d", &x);
		mart.pb(x);
	}
	rep(i, m) {
		int x, y, z; scanf("%d%d%d", &x, &y, &z);
		E[x].pb(pii(z, y));
		E[y].pb(pii(z, x));
	}
	priority_queue <t3, vector<t3>, greater<t3> > pq;
	for(int e : mart) {
		M[e].pb(pii(0, e));
		pq.push(t3(0, e, e));
	}
	int cnt[50050] = {};
	while(!pq.empty()) {
		t3 t = pq.top(); pq.pop();
		int v = get<1>(t), s = get<2>(t);
		int L = get<0>(t);
		if(cnt[v] > 11) continue;
		int ok = 0;
		for(pii e : M[v]) if(e.Fi == L && e.Se == s){ ok = 1; break; }
		if(ok == 0) continue;
		++cnt[v];
		
		for(pii e : E[v]) {
			int flag = 0;
			for(pii &f : M[e.Se]) if(f.Se == s) {
				flag = 1;
				if(f.Fi > L + e.Fi) {
					f.Fi = L + e.Fi;
					pq.push(t3(L + e.Fi, e.Se, s));
				}
				break;
			}
			if(flag == 0) {
				M[e.Se].pb(pii(L + e.Fi, s));
				for(int i=sz(M[e.Se])-1;i;i--) {
					if(M[e.Se][i-1] > M[e.Se][i]) swap(M[e.Se][i], M[e.Se][i-1]);
					else break;
				}
				if(sz(M[e.Se]) > 11) M[e.Se].pop_back();
				pq.push(t3(L + e.Fi, e.Se, s));
			}
		}
	}
	int chk[50050] = {};
	while(q--) {
		int s, r; scanf("%d%d", &s, &r);
		set <int> v;
		rep(a, r) {
			int x; scanf("%d", &x); chk[x] = q + 10;
		}
		pii ans = pii(2e9, -1);
		//for(pii e : M[s]) printf("%d,%d\n", e.Fi, e.Se); puts("");
		for(pii e : M[s]) if(chk[e.Se] != q + 10 && ans.Fi > e.Fi) ans.Fi = e.Fi, ans.Se = e.Se;
		printf("%d %d\n", ans.Se, ans.Fi);
	}
}

int main(){
	int tc = 1; // scanf("%d", &tc);
	for(int t=1;t<=tc;t++) {
		solve();
	}
	return 0;
};

Compilation message

mart.cpp: In function 'void solve()':
mart.cpp:40:35: 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:42:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x);
                         ^
mart.cpp:46:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y, z; scanf("%d%d%d", &x, &y, &z);
                                           ^
mart.cpp:89:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int s, r; scanf("%d%d", &s, &r);
                                  ^
mart.cpp:92:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d", &x); chk[x] = q + 10;
                          ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4640 KB Output is correct
2 Correct 0 ms 4636 KB Output is correct
3 Correct 0 ms 4640 KB Output is correct
4 Correct 0 ms 4632 KB Output is correct
5 Incorrect 0 ms 4636 KB Output isn't correct
6 Halted 0 ms 0 KB -