oj.uz

답안 #25604

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25604 2017-06-23T07:57:33 Z 김동현(#1072) 한자 끝말잇기 (JOI14_kanji) C++14
0 / 100
 662 ms 21704 KB 
#include "Annalib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct E{
	int x;
	ll d;
	bool operator<(const E &oth) const {
		return d > oth.d;
	}
};

const static ll inf = 4e18;
const static int six[3] = {1, 6, 36};
static int n, sp[300][300], vis[300], brn[20];
static ll md[300];
static vector<E> e[300];
static vector<int> t[300][300];
static priority_queue<E> pq;

static void mak(int k, int x){
	vis[x] = 1;
	for(auto &i : e[x]){
		if(vis[i.x]) continue;
		if(md[i.x] == md[x] + i.d){
			t[k][x].push_back(i.x);
			mak(k, i.x);
		}
	}
}

static void dijk(int x){
	fill(md, md + n, inf);
	md[x] = 0;
	pq.push({x, 0});
	while(!pq.empty()){
		E c = pq.top(); pq.pop();
		for(auto &i : e[c.x]){
			if(md[i.x] > c.d + i.d){
				md[i.x] = c.d + i.d;
				pq.push({i.x, md[i.x]});
			}
		}
	}
	fill(vis, vis + n, 0);
	//for(int i = 0; i < n; i++) printf("%lld ", md[i]);
	//puts("");
	mak(x, x);
	//for(int i = 0; i < n; i++, puts("")) for(auto &j : t[x][i]) printf("%d ", j);
}

static int fnd(int s, int x, int y){
	if(x == y) return 0;
	for(auto &i : t[s][x]){
		int t = fnd(s, i, y);
		if(t >= 0){
			return max(t, sp[x][i]);
		}
	}
	return -1;
}

void Anna(int N, int M, int A[], int B[], ll C[], int Q, int S[], int T[], int K, int U[]) {
	n = N;
	for(int i = 0; i < M; i++){
		e[A[i]].push_back({B[i], C[i]});
		for(int j = 0; j < K; j++){
			if(U[j] == i){
				sp[A[i]][B[i]] = j + 1;
			}
		}
	}
	for(int i = 0; i < N; i++) dijk(i);
	//puts("----");
	for(int i = 0; i < Q; i++){
		//printf("%d : %d\n", i, fnd(S[i], S[i], T[i]));
		brn[i / 3] = fnd(S[i], S[i], T[i]) * six[i % 3];
	}
	for(int i = 0; i < 20; i++){
		for(int j = 0; j < 8; j++) Tap(!!(brn[i] & (1 << j)));
	}
	//puts("------------");
}

#include "Brunolib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct E{
	int x;
	ll d;
	bool operator<(const E &oth) const {
		return d > oth.d;
	}
};

const static ll inf = 4e18;
static int n, vis[300], qa[60], id[6][2], en[300][300], fl;
static ll md[300];
static vector<E> e[300];
static vector<int> t[60][300], av;
static priority_queue<E> pq;

static void mak(int k, int x){
	vis[x] = 1;
	for(auto &i : e[x]){
		if(vis[i.x]) continue;
		if(md[i.x] == md[x] + i.d){
			t[k][x].push_back(i.x);
			mak(k, i.x);
		}
	}
}

static void dijk(int cnt, int x){
	fill(md, md + n, inf);
	md[x] = 0;
	pq.push({x, 0});
	while(!pq.empty()){
		E c = pq.top(); pq.pop();
		for(auto &i : e[c.x]){
			if(md[i.x] > c.d + i.d){
				md[i.x] = c.d + i.d;
				pq.push({i.x, md[i.x]});
			}
		}
	}
	//for(int i = 0; i < n; i++) printf("%lld ", md[i]);
	fill(vis, vis + n, 0);
	mak(cnt, x);
	//for(int i = 0; i < n; i++, puts("")) for(auto &j : t[cnt][i]) printf("%d ", j);
}

static void ans(int cnt, int x, int y){
	//printf("ans %d %d %d\n", cnt, x, y);
	if(x == y){
		//printf("%d : ", cnt);
		for(auto &i : av){ /*printf("%d ", i);*/ Answer(i); }
		//puts("");
		Answer(-1);
		return;
	}
	for(auto &i : t[cnt][x]){
		av.push_back(en[x][i]);
		ans(cnt, i, y);
		av.pop_back();
	}
}


void Bruno(int N, int M, int A[], int B[], ll C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) {
	n = N;
	for(int i = 0; i < M; i++){
		e[A[i]].push_back({B[i], C[i]});
		en[A[i]][B[i]] = i;
		for(int j = 0; j < K; j++){
			if(U[j] == i){
				e[A[i]].back().d = inf;
				id[j + 1][0] = A[i];
				id[j + 1][1] = (int)e[A[i]].size() - 1;
			}
		}
	}
	for(int i = 0; i < L; i += 8){
		int t = 0;
		for(int j = 0; j < 8; j++) t += X[i + j] * (1 << j);
		for(int j = 0; j < 3; j++, t /= 6) qa[i / 8 * 3 + j] = t % 6;
	}
	for(int i = 0; i < Q; i++){
		if(qa[i]) e[id[qa[i]][0]][id[qa[i]][1]].d = 0;
		dijk(i, S[i]);
		//puts("-----");
		ans(i, S[i], T[i]);
		//puts("-----");
		if(qa[i]) e[id[qa[i]][0]][id[qa[i]][1]].d = inf;
	}
}

Compilation message

Bruno.cpp:15:57: warning: 'fl' defined but not used [-Wunused-variable]
 static int n, vis[300], qa[60], id[6][2], en[300][300], fl;
                                                         ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 16352 KB Output isn't correct - Wrong Answer [9]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 18068 KB Output isn't correct - Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 18068 KB Output isn't correct - Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 18068 KB Output isn't correct - Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 18068 KB Output isn't correct - Wrong Answer [5]
2 Incorrect 28 ms 18068 KB Output isn't correct - Wrong Answer [5]
3 Incorrect 13 ms 18068 KB Output isn't correct - Wrong Answer [5]
4 Incorrect 16 ms 18200 KB Output isn't correct - Wrong Answer [5]
5 Incorrect 13 ms 16616 KB Output isn't correct - Wrong Answer [9]
6 Incorrect 19 ms 16484 KB Output isn't correct - Wrong Answer [9]
7 Incorrect 16 ms 16484 KB Output isn't correct - Wrong Answer [9]
8 Incorrect 19 ms 16484 KB Output isn't correct - Wrong Answer [9]
9 Incorrect 3 ms 15692 KB Output isn't correct - Wrong Answer [9]
10 Incorrect 9 ms 15692 KB Output isn't correct - Wrong Answer [9]
11 Incorrect 13 ms 15692 KB Output isn't correct - Wrong Answer [9]
12 Incorrect 19 ms 16616 KB Output isn't correct - L = 160
13 Incorrect 662 ms 21704 KB Output isn't correct - L = 160
14 Incorrect 19 ms 16616 KB Output isn't correct - Wrong Answer [5]
15 Incorrect 25 ms 16616 KB Output isn't correct - Wrong Answer [5]
16 Incorrect 38 ms 16880 KB Output isn't correct - Wrong Answer [9]
17 Incorrect 52 ms 16880 KB Output isn't correct - Wrong Answer [9]
18 Incorrect 79 ms 16880 KB Output isn't correct - Wrong Answer [9]
19 Incorrect 19 ms 15956 KB Output isn't correct - Wrong Answer [5]
20 Incorrect 52 ms 16352 KB Output isn't correct - L = 160
21 Incorrect 98 ms 17276 KB Output isn't correct - L = 160
22 Incorrect 6 ms 15692 KB Output isn't correct - Wrong Answer [9]
23 Incorrect 3 ms 15692 KB Output isn't correct - Wrong Answer [9]
24 Incorrect 6 ms 15692 KB Output isn't correct - Wrong Answer [9]