| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 25615 |
2017-06-23T08:19:53 Z |
서규호(#1074) |
한자 끝말잇기 (JOI14_kanji) |
C++14 |
|
249 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,cnt = 0;
for(int i=1; i<=L; i+=8){
int tsum = 0;
two = 1;
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){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
11896 KB |
Output is correct - L = 32 |
| 2 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 32 |
| 3 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 32 |
| 4 |
Correct |
0 ms |
11896 KB |
Output is correct - L = 32 |
| 5 |
Correct |
0 ms |
11896 KB |
Output is correct - L = 32 |
| 6 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 32 |
| 7 |
Correct |
0 ms |
11896 KB |
Output is correct - L = 32 |
| 8 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 32 |
| 9 |
Correct |
0 ms |
12160 KB |
Output is correct - L = 32 |
| 10 |
Correct |
6 ms |
12160 KB |
Output is correct - L = 32 |
| 11 |
Correct |
0 ms |
11896 KB |
Output is correct - L = 8 |
| 12 |
Correct |
165 ms |
19840 KB |
Output is correct - L = 32 |
| 13 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 32 |
| 14 |
Correct |
0 ms |
11896 KB |
Output is correct - L = 8 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 2 |
Correct |
0 ms |
11896 KB |
Output is correct - L = 160 |
| 3 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 160 |
| 4 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 5 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 6 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 7 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 8 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 9 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 10 |
Correct |
0 ms |
11896 KB |
Output is correct - L = 160 |
| 11 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 160 |
| 12 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 160 |
| 13 |
Correct |
249 ms |
19848 KB |
Output is correct - L = 160 |
| 14 |
Correct |
9 ms |
11896 KB |
Output is correct - L = 160 |
| 15 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 16 |
Correct |
15 ms |
12160 KB |
Output is correct - L = 160 |
| 17 |
Correct |
28 ms |
12160 KB |
Output is correct - L = 160 |
| 18 |
Correct |
32 ms |
12424 KB |
Output is correct - L = 160 |
| 19 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 160 |
| 20 |
Correct |
22 ms |
12688 KB |
Output is correct - L = 160 |
| 21 |
Correct |
39 ms |
12688 KB |
Output is correct - L = 160 |
| 22 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 160 |
| 23 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 160 |
| 24 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 160 |
| 2 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 3 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 4 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 160 |
| 5 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 6 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 7 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 8 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 160 |
| 9 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 160 |
| 10 |
Correct |
0 ms |
11896 KB |
Output is correct - L = 160 |
| 11 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 160 |
| 12 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 13 |
Correct |
192 ms |
19848 KB |
Output is correct - L = 160 |
| 14 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 15 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 16 |
Correct |
22 ms |
12160 KB |
Output is correct - L = 160 |
| 17 |
Correct |
26 ms |
12160 KB |
Output is correct - L = 160 |
| 18 |
Correct |
32 ms |
12424 KB |
Output is correct - L = 160 |
| 19 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 160 |
| 20 |
Correct |
22 ms |
12688 KB |
Output is correct - L = 160 |
| 21 |
Correct |
41 ms |
12688 KB |
Output is correct - L = 160 |
| 22 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| 23 |
Correct |
3 ms |
11896 KB |
Output is correct - L = 160 |
| 24 |
Correct |
6 ms |
11896 KB |
Output is correct - L = 160 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11896 KB |
Output isn't correct - L = 160 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
11896 KB |
Output isn't correct - L = 160 |
| 2 |
Incorrect |
6 ms |
11896 KB |
Output isn't correct - L = 160 |
| 3 |
Incorrect |
3 ms |
11896 KB |
Output isn't correct - L = 160 |
| 4 |
Incorrect |
0 ms |
11896 KB |
Output isn't correct - L = 160 |
| 5 |
Incorrect |
6 ms |
11896 KB |
Output isn't correct - L = 160 |
| 6 |
Incorrect |
6 ms |
11896 KB |
Output isn't correct - L = 160 |
| 7 |
Incorrect |
3 ms |
11896 KB |
Output isn't correct - L = 160 |
| 8 |
Incorrect |
6 ms |
11896 KB |
Output isn't correct - L = 160 |
| 9 |
Incorrect |
6 ms |
11896 KB |
Output isn't correct - L = 160 |
| 10 |
Incorrect |
6 ms |
11896 KB |
Output isn't correct - L = 160 |
| 11 |
Incorrect |
3 ms |
11896 KB |
Output isn't correct - L = 160 |
| 12 |
Incorrect |
6 ms |
11896 KB |
Output isn't correct - L = 160 |
| 13 |
Incorrect |
229 ms |
19848 KB |
Output isn't correct - L = 160 |
| 14 |
Incorrect |
6 ms |
11896 KB |
Output isn't correct - L = 160 |
| 15 |
Incorrect |
6 ms |
11896 KB |
Output isn't correct - L = 160 |
| 16 |
Incorrect |
15 ms |
12160 KB |
Output isn't correct - L = 160 |
| 17 |
Incorrect |
22 ms |
12160 KB |
Output isn't correct - L = 160 |
| 18 |
Incorrect |
19 ms |
12424 KB |
Output isn't correct - L = 160 |
| 19 |
Incorrect |
3 ms |
11896 KB |
Output isn't correct - L = 160 |
| 20 |
Incorrect |
28 ms |
12688 KB |
Output isn't correct - L = 160 |
| 21 |
Incorrect |
41 ms |
12688 KB |
Output isn't correct - L = 160 |
| 22 |
Incorrect |
3 ms |
11896 KB |
Output isn't correct - L = 160 |
| 23 |
Incorrect |
6 ms |
11896 KB |
Output isn't correct - L = 160 |
| 24 |
Incorrect |
3 ms |
11896 KB |
Output isn't correct - L = 160 |
