Submission #28631

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
28631	2017-07-16T08:13:40 Z	쥬니님일어나세요 버스운전해주시기로했잖아요(#1179, kjp4155, pjh0123, dnsdhrj)	Alternative Mart (FXCUP2_mart)	C++14	0 / 1	5000 ms	128044 KB

mart

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll,ll> Pll;

#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 repp(i, n) for(int i=1;i<=n;i++)
#define all(x) x.begin(), x.end()

#define geti1(X) scanf("%d",&X)
#define geti2(X,Y) scanf("%d%d",&X,&Y)
#define geti3(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
#define geti4(X,Y,Z,W) scanf("%d%d%d%d",&X,&Y,&Z,&W)

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__)

#define INF 987654321
#define IINF 87654321987654321
#define MAXV 200500


#define MOD 1234567
int N,M,K,T;
vector<int> pos;
vector<Pll> E[60000];
ll dist[60000]; int pa[60000];
bool vis[60000];
set<int> used[60000];
set<Pll> s[60000];
typedef pair<ll,Pll> ppll;
int main(){
	rep(i,60000) dist[i] = IINF;
	geti(N,M,K,T);
	repp(i,K){
		int x; geti(x); pos.pb(x);
	}

	repp(i,M){
		ll a,b,c; scanf("%lld%lld%lld",&a,&b,&c);
		E[a].push_back({b,c}); E[b].push_back({a,c});
	}

	priority_queue<ppll, vector<ppll>, greater<ppll>> pq;
	
	for(auto e : pos){
		pq.push({0,{e,e}}); dist[e] = 0; vis[e] =true;
		pa[e] = e; used[e].insert(e);
		s[e].insert({0,e});
	}

	while(!pq.empty()){
		ll curd = pq.top().Fi; int cur = pq.top().Se.Fi;
		int p = pq.top().Se.Se;
		pq.pop();
		if( used[cur].find(p) == used[cur].end() ){
			used[cur].insert(p);
			s[cur].insert({curd,p});
		}
		else{
			bool ok = true;
			for(auto e : s[cur]){
				if( e.Se == p && e.Fi < curd ){
					ok = false;
					break;
				}
			}
			if( !ok ) continue;
		}
		for(auto e : E[cur]){
			if( used[e.Fi].size() >= 11 ) continue;
			if( used[e.Fi].find( p ) != used[e.Fi].end() ) continue;
			//used[e.Fi].insert(p);
			//s[e.Fi].insert({curd+e.Se,p});
			pq.push({curd+e.Se,{e.Fi,p}});
		}
	} 

	/*
	repp(i,N){
		for(auto e : s[i]){
			cout << i << " " << e.Fi << " " << e.Se << endl;
		}
	}
*/
	//cout << T << endl;
	repp(i,T){
		int S; geti(S);
		int X; geti(X);
		set<int> die;
		repp(i,X){
			int y; geti(y); die.insert(y);
		}
		//for(auto e : die) printf("[%d]",e);
		bool ok = false;
		for(auto e : s[S]){
			if( die.find(e.Se) == die.end() ){
				printf("%lld %lld\n",e.Se,e.Fi);
				//printf("!");
				ok = true;
				break;
			}
		
		}

	}





}	

Compilation message

mart.cpp: In function 'int main()':
mart.cpp:116:8: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
   bool ok = false;
        ^
mart.cpp:55:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  geti(N,M,K,T);
               ^
mart.cpp:57:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; geti(x); pos.pb(x);
                 ^
mart.cpp:61:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll a,b,c; scanf("%lld%lld%lld",&a,&b,&c);
                                           ^
mart.cpp:109:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int S; geti(S);
                 ^
mart.cpp:110:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int X; geti(X);
                 ^
mart.cpp:113:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int y; geti(y); die.insert(y);
                  ^

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	9820 KB	Output is correct
2	Correct	0 ms	9820 KB	Output is correct
3	Correct	3 ms	9820 KB	Output is correct
4	Correct	0 ms	9820 KB	Output is correct
5	Correct	0 ms	9956 KB	Output is correct
6	Correct	6 ms	9956 KB	Output is correct
7	Correct	3 ms	10620 KB	Output is correct
8	Correct	6 ms	10480 KB	Output is correct
9	Correct	823 ms	30096 KB	Output is correct
10	Correct	46 ms	15208 KB	Output is correct
11	Correct	96 ms	17652 KB	Output is correct
12	Correct	99 ms	16156 KB	Output is correct
13	Execution timed out	5000 ms	128044 KB	Execution timed out
14	Halted	0 ms	0 KB	-