Submission #25607

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
25607	2017-06-23T08:06:17 Z	서규호(#1074)	한자 끝말잇기 (JOI14_kanji)	C++14	32 / 100	229 ms	19848 KB

Anna

#include "Annalib.h"
#include <bits/stdc++.h>

#define lld long long
#define Linf 4000000000000000000LL
#define pb push_back

using namespace std;

static int N,M,Q,K;
static vector<pair<pair<int,lld>,int>> word[302];
static int s[62],t[62];
static priority_queue<pair<lld,int>,vector<pair<lld,int>>,greater<pair<lld,int>>> q;
static bool check[302],forgot[90000];
static lld d[302];
static pair<int,int> path[302];

static vector<int> process(int num){
	for(int i=1; i<=N; i++) d[i] = Linf, check[i] = false;
	d[s[num]] = 0; q.push({0,s[num]});
	while(!q.empty()){
		int v = q.top().second;
		q.pop();
		if(check[v]) continue;
		check[v] = true;
		for(auto &i : word[v]){
			if(check[i.first.first] || d[i.first.first] <= d[v]+i.first.second) continue;
			d[i.first.first] = d[v]+i.first.second;
			q.push({d[i.first.first],i.first.first});
			path[i.first.first] = {v,i.second};
		}
	}
	vector<int> tmp;
	int x = t[num];
	while(x != s[num]){
		tmp.pb(path[x].second);
		x = path[x].first;
	}
	reverse(tmp.begin(),tmp.end());
	return tmp;
}

static void send(int x){
	Tap(x/4); x %= 4;
	Tap(x/2); x %= 2;
	Tap(x/1);
}

void Anna(int n, int m, int A[], int B[], long long C[], int q, int S[], int T[], int k, int U[]) {
	N = n; M = m; Q = q; K = k;
	for(int i=1; i<=M; i++){
		word[A[i-1]+1].pb({{B[i-1]+1,C[i-1]},i-1});
	}
	for(int i=1; i<=Q; i++){
		s[i] = S[i-1]+1; t[i] = T[i-1]+1;
	}
	for(int i=1; i<=K; i++) forgot[U[i-1]] = true;
	for(int i=1; i<=Q; i++){
		vector<int> get = process(i);
		bool flag = false;
		for(auto &j : get){
			if(!forgot[j]) continue;
			flag = true;
			for(int k=0; k<K; k++){
				if(j == U[k]) send(k+1);
			}
		}
		if(!flag) send(0);
	}
}

Bruno

#include "Brunolib.h"
#include <bits/stdc++.h>

#define lld long long
#define Linf 4000000000000000000LL
#define pb push_back

using namespace std;

static int N,M,Q,K,L;
static vector<pair<pair<int,lld>,int>> word[302];
static int s[62],t[62];
static priority_queue<pair<lld,int>,vector<pair<lld,int>>,greater<pair<lld,int>>> q;
static bool check[302];
static lld d[302];
static pair<int,int> path[302];
static int x[1002];

static vector<int> process(int start,int end){
	for(int i=1; i<=N; i++) d[i] = Linf, check[i] = false;
	d[start] = 0; q.push({0,start});
	while(!q.empty()){
		int v = q.top().second;
		q.pop();
		if(check[v]) continue;
		check[v] = true;
		for(auto &i : word[v]){
			if(check[i.first.first] || d[i.first.first] <= d[v]+i.first.second) continue;
			d[i.first.first] = d[v]+i.first.second;
			q.push({d[i.first.first],i.first.first});
			path[i.first.first] = {v,i.second};
		}
	}
	vector<int> tmp;
	if(d[end] == Linf) return tmp;
	int x = end;
	while(x != start){
		tmp.pb(path[x].second);
		x = path[x].first;
	}
	reverse(tmp.begin(),tmp.end());
	return tmp;
}

static int cnt = 1;
static int decoding(){
	int tsum;
	tsum = x[cnt]*4+x[cnt+1]*2+x[cnt+2];
	cnt += 3;
	return tsum;
}

void Bruno(int n, int m, int A[], int B[], long long C[], int q, int S[], int T[], int k, int U[], int l, int X[]) {
	N = n; M = m; Q = q; K = k; L = l;
	for(int i=1; i<=K; i++){
		C[U[i-1]] = Linf;
	}
	for(int i=1; i<=M; i++){
		word[A[i-1]+1].pb({{B[i-1]+1,C[i-1]},i-1});
	}
	for(int i=1; i<=Q; i++){
		s[i] = S[i-1]+1; t[i] = T[i-1]+1;
	}
	for(int i=1; i<=L; i++) x[i] = X[i-1];
	for(int i=1; i<=Q; i++){
		int decode = decoding();
		vector<int> get,print;
		if(decode == 0){
			print = process(s[i],t[i]);
		}else{
			get = process(s[i],A[U[decode-1]]+1);
			for(auto &j : get) print.pb(j);
			print.pb(U[decode-1]);
			get.clear();
			get = process(B[U[decode-1]]+1,t[i]);
			for(auto &j : get) print.pb(j);
		}
		print.pb(-1);
		for(auto &j : print){
			Answer(j);
		}
	}
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	11896 KB	Output is correct - L = 30
2	Correct	3 ms	11896 KB	Output is correct - L = 30
3	Correct	0 ms	11896 KB	Output is correct - L = 30
4	Correct	0 ms	11896 KB	Output is correct - L = 30
5	Correct	3 ms	11896 KB	Output is correct - L = 30
6	Correct	0 ms	11896 KB	Output is correct - L = 30
7	Correct	0 ms	11896 KB	Output is correct - L = 30
8	Correct	6 ms	11896 KB	Output is correct - L = 30
9	Correct	0 ms	12160 KB	Output is correct - L = 30
10	Correct	9 ms	12160 KB	Output is correct - L = 30
11	Correct	0 ms	11896 KB	Output is correct - L = 3
12	Correct	179 ms	19840 KB	Output is correct - L = 30
13	Correct	3 ms	11896 KB	Output is correct - L = 30
14	Correct	0 ms	11896 KB	Output is correct - L = 3

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	11896 KB	Output is correct - L = 180
2	Correct	3 ms	11896 KB	Output is correct - L = 180
3	Correct	6 ms	11896 KB	Output is correct - L = 180
4	Correct	3 ms	11896 KB	Output is correct - L = 180
5	Correct	3 ms	11896 KB	Output is correct - L = 180
6	Correct	6 ms	11896 KB	Output is correct - L = 180
7	Correct	3 ms	11896 KB	Output is correct - L = 180
8	Correct	3 ms	11896 KB	Output is correct - L = 180
9	Correct	3 ms	11896 KB	Output is correct - L = 180
10	Correct	6 ms	11896 KB	Output is correct - L = 180
11	Correct	3 ms	11896 KB	Output is correct - L = 180
12	Correct	6 ms	11896 KB	Output is correct - L = 180
13	Correct	229 ms	19848 KB	Output is correct - L = 180
14	Correct	6 ms	11896 KB	Output is correct - L = 180
15	Correct	0 ms	11896 KB	Output is correct - L = 180
16	Correct	9 ms	12160 KB	Output is correct - L = 180
17	Correct	19 ms	12160 KB	Output is correct - L = 180
18	Correct	28 ms	12424 KB	Output is correct - L = 180
19	Correct	3 ms	11896 KB	Output is correct - L = 180
20	Correct	22 ms	12688 KB	Output is correct - L = 180
21	Correct	32 ms	12688 KB	Output is correct - L = 180
22	Correct	3 ms	11896 KB	Output is correct - L = 180
23	Correct	3 ms	11896 KB	Output is correct - L = 180
24	Correct	3 ms	11896 KB	Output is correct - L = 180

Subtask #3

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	11896 KB	Output isn't correct - L = 180
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	11896 KB	Output isn't correct - L = 180
2	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	11896 KB	Output isn't correct - L = 180
2	Incorrect	6 ms	11896 KB	Output isn't correct - L = 180
3	Incorrect	6 ms	11896 KB	Output isn't correct - L = 180
4	Incorrect	6 ms	11896 KB	Output isn't correct - L = 180
5	Incorrect	6 ms	11896 KB	Output isn't correct - L = 180
6	Incorrect	9 ms	11896 KB	Output isn't correct - L = 180
7	Incorrect	6 ms	11896 KB	Output isn't correct - L = 180
8	Incorrect	3 ms	11896 KB	Output isn't correct - L = 180
9	Incorrect	3 ms	11896 KB	Output isn't correct - L = 180
10	Incorrect	0 ms	11896 KB	Output isn't correct - L = 180
11	Incorrect	3 ms	11896 KB	Output isn't correct - L = 180
12	Incorrect	3 ms	11896 KB	Output isn't correct - L = 180
13	Incorrect	219 ms	19848 KB	Output isn't correct - L = 180
14	Incorrect	6 ms	11896 KB	Output isn't correct - L = 180
15	Incorrect	0 ms	11896 KB	Output isn't correct - L = 180
16	Incorrect	15 ms	12160 KB	Output isn't correct - L = 180
17	Incorrect	19 ms	12160 KB	Output isn't correct - L = 180
18	Incorrect	25 ms	12424 KB	Output isn't correct - L = 180
19	Incorrect	3 ms	11896 KB	Output isn't correct - L = 180
20	Incorrect	27 ms	12688 KB	Output isn't correct - L = 180
21	Incorrect	32 ms	12688 KB	Output isn't correct - L = 180
22	Incorrect	6 ms	11896 KB	Output isn't correct - L = 180
23	Incorrect	0 ms	11896 KB	Output isn't correct - L = 180
24	Incorrect	3 ms	11896 KB	Output isn't correct - L = 180