oj.uz

Submission #25612

# Submission time Handle Problem Language Result Execution time Memory
25612 2017-06-23T08:14:59 Z 서규호(#1074) 한자 끝말잇기 (JOI14_kanji) C++14
0 / 100
 215 ms 19848 KB 
#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> send;

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;
}

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.pb(k+1);
			}
		}
		if(!flag) send.pb(0);
	}
	while(send.size()%3 != 0) send.pb(0);
	for(int i=0; i<send.size(); i+=3){
		int tsum;
		tsum = 36*send[i]+6*send[i+1]+send[i+2];
		for(int j=1; j<=8; j++){
			Tap(tsum%2);
			tsum /= 2;
		}
	}
}

#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],decode[70];

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 void decoding(){
	int two = 1,cnt = 0;
	for(int i=1; i<=L; i+=8){
		int tsum = 0;
		for(int j=0; j<8; j++){
			tsum += two*x[i+j];
			two *= 2;
		}
		decode[++cnt] = tsum/36; tsum %= 36;
		decode[++cnt] = tsum/6; tsum %= 6;
		decode[++cnt] = 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];
	decoding();
	for(int i=1; i<=Q; i++){
		vector<int> get,print;
		if(decode[i] == 0){
			print = process(s[i],t[i]);
		}else{
			get = process(s[i],A[U[decode[i]-1]]+1);
			for(auto &j : get) print.pb(j);
			print.pb(U[decode[i]-1]);
			get.clear();
			get = process(B[U[decode[i]-1]]+1,t[i]);
			for(auto &j : get) print.pb(j);
		}
		print.pb(-1);
		for(auto &j : print){
			Answer(j);
		}
	}
}

Compilation message

Anna.cpp: In function 'void Anna(int, int, int*, int*, long long int*, int, int*, int*, int, int*)':
Anna.cpp:66:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<send.size(); i+=3){
                ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 3 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 6 ms 11896 KB Output isn't correct - Wrong Answer [6]
4 Incorrect 3 ms 11896 KB Output isn't correct - Wrong Answer [6]
5 Runtime error 0 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 6 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 6 ms 11896 KB Output isn't correct - Wrong Answer [9]
8 Incorrect 3 ms 11896 KB Output isn't correct - Wrong Answer [9]
9 Runtime error 0 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 0 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 3 ms 11896 KB Output isn't correct - L = 160
13 Incorrect 215 ms 19848 KB Output isn't correct - L = 160
14 Runtime error 3 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Incorrect 6 ms 11896 KB Output isn't correct - Wrong Answer [6]
16 Runtime error 6 ms 12160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 9 ms 12160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 19 ms 12424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 0 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Incorrect 15 ms 12688 KB Output isn't correct - L = 160
21 Incorrect 32 ms 12688 KB Output isn't correct - L = 160
22 Runtime error 3 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 3 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 3 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)