oj.uz

답안 #25603

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25603 2017-06-23T07:56:49 Z 김동현(#1072) 한자 끝말잇기 (JOI14_kanji) C++14
0 / 100
 453 ms 18896 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 16220 KB Do not print anything to standard output
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 17672 KB Do not print anything to standard output
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 17672 KB Do not print anything to standard output
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 17672 KB Do not print anything to standard output
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 17672 KB Do not print anything to standard output
2 Incorrect 13 ms 17672 KB Do not print anything to standard output
3 Incorrect 13 ms 17672 KB Do not print anything to standard output
4 Incorrect 13 ms 17672 KB Do not print anything to standard output
5 Incorrect 16 ms 16352 KB Do not print anything to standard output
6 Incorrect 13 ms 16220 KB Do not print anything to standard output
7 Incorrect 13 ms 16220 KB Do not print anything to standard output
8 Incorrect 16 ms 16220 KB Do not print anything to standard output
9 Incorrect 9 ms 15560 KB Do not print anything to standard output
10 Incorrect 6 ms 15560 KB Do not print anything to standard output
11 Incorrect 13 ms 15560 KB Do not print anything to standard output
12 Incorrect 16 ms 16352 KB Do not print anything to standard output
13 Incorrect 453 ms 18896 KB Do not print anything to standard output
14 Incorrect 19 ms 16352 KB Do not print anything to standard output
15 Incorrect 16 ms 16352 KB Do not print anything to standard output
16 Incorrect 29 ms 16484 KB Do not print anything to standard output
17 Incorrect 33 ms 16484 KB Do not print anything to standard output
18 Incorrect 53 ms 16484 KB Do not print anything to standard output
19 Incorrect 3 ms 15824 KB Do not print anything to standard output
20 Incorrect 36 ms 15956 KB Do not print anything to standard output
21 Incorrect 79 ms 16748 KB Do not print anything to standard output
22 Incorrect 9 ms 15560 KB Do not print anything to standard output
23 Incorrect 6 ms 15560 KB Do not print anything to standard output
24 Incorrect 6 ms 15560 KB Do not print anything to standard output