oj.uz

Submission #25606

# Submission time Handle Problem Language Result Execution time Memory
25606 2017-06-23T08:04:55 Z 김동현(#1072) 한자 끝말잇기 (JOI14_kanji) C++14
40 / 100
 629 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];
	}
	//puts("---");
	for(int i = 0; i < 20; i++){
		//printf("%d : %d\n", i, brn[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;
			}
		}
	}
	//puts("---");
	for(int i = 0; i < L; i += 8){
		int t = 0;
		for(int j = 0; j < 8; j++) t += X[i + j] * (1 << j);
		//printf("%d : %d\n", i / 8, t);
		for(int j = 0; j < 3; j++, t /= 6) qa[i / 8 * 3 + j] = t % 6;
	}
	//puts("-----");
	for(int i = 0; i < Q; i++){
		//printf("%d : %d\n", i, qa[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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 16352 KB Output is correct - L = 160
2 Correct 12 ms 16484 KB Output is correct - L = 160
3 Correct 16 ms 16352 KB Output is correct - L = 160
4 Correct 16 ms 17804 KB Output is correct - L = 160
5 Correct 16 ms 17804 KB Output is correct - L = 160
6 Correct 16 ms 17804 KB Output is correct - L = 160
7 Correct 6 ms 17672 KB Output is correct - L = 160
8 Correct 16 ms 16616 KB Output is correct - L = 160
9 Correct 26 ms 16616 KB Output is correct - L = 160
10 Correct 49 ms 16616 KB Output is correct - L = 160
11 Correct 13 ms 16088 KB Output is correct - L = 160
12 Correct 562 ms 21588 KB Output is correct - L = 160
13 Correct 13 ms 15956 KB Output is correct - L = 160
14 Correct 9 ms 17804 KB Output is correct - L = 160

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 18068 KB Output is correct - L = 160
2 Correct 9 ms 18200 KB Output is correct - L = 160
3 Correct 12 ms 18200 KB Output is correct - L = 160
4 Correct 9 ms 18200 KB Output is correct - L = 160
5 Correct 9 ms 16616 KB Output is correct - L = 160
6 Correct 16 ms 16484 KB Output is correct - L = 160
7 Correct 13 ms 16484 KB Output is correct - L = 160
8 Correct 16 ms 16484 KB Output is correct - L = 160
9 Correct 9 ms 15692 KB Output is correct - L = 160
10 Correct 9 ms 15692 KB Output is correct - L = 160
11 Correct 6 ms 15692 KB Output is correct - L = 160
12 Correct 22 ms 16616 KB Output is correct - L = 160
13 Correct 554 ms 21704 KB Output is correct - L = 160
14 Correct 22 ms 16616 KB Output is correct - L = 160
15 Correct 19 ms 16616 KB Output is correct - L = 160
16 Correct 23 ms 16880 KB Output is correct - L = 160
17 Correct 52 ms 16880 KB Output is correct - L = 160
18 Correct 62 ms 16880 KB Output is correct - L = 160
19 Correct 13 ms 16088 KB Output is correct - L = 160
20 Correct 45 ms 16352 KB Output is correct - L = 160
21 Correct 108 ms 17276 KB Output is correct - L = 160
22 Correct 12 ms 15692 KB Output is correct - L = 160
23 Correct 6 ms 15692 KB Output is correct - L = 160
24 Correct 6 ms 15692 KB Output is correct - L = 160

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 18068 KB Output is correct - L = 160
2 Correct 9 ms 18200 KB Output is correct - L = 160
3 Correct 19 ms 18200 KB Output is correct - L = 160
4 Correct 16 ms 18200 KB Output is correct - L = 160
5 Correct 12 ms 16616 KB Output is correct - L = 160
6 Correct 16 ms 16484 KB Output is correct - L = 160
7 Correct 16 ms 16484 KB Output is correct - L = 160
8 Correct 16 ms 16484 KB Output is correct - L = 160
9 Correct 6 ms 15692 KB Output is correct - L = 160
10 Correct 6 ms 15692 KB Output is correct - L = 160
11 Correct 6 ms 15692 KB Output is correct - L = 160
12 Correct 19 ms 16616 KB Output is correct - L = 160
13 Correct 629 ms 21704 KB Output is correct - L = 160
14 Correct 19 ms 16616 KB Output is correct - L = 160
15 Correct 22 ms 16616 KB Output is correct - L = 160
16 Correct 28 ms 16880 KB Output is correct - L = 160
17 Correct 45 ms 16880 KB Output is correct - L = 160
18 Correct 62 ms 16880 KB Output is correct - L = 160
19 Correct 6 ms 16088 KB Output is correct - L = 160
20 Correct 59 ms 16352 KB Output is correct - L = 160
21 Correct 102 ms 17276 KB Output is correct - L = 160
22 Correct 3 ms 15692 KB Output is correct - L = 160
23 Correct 12 ms 15692 KB Output is correct - L = 160
24 Correct 12 ms 15692 KB Output is correct - L = 160

Subtask #4
0 / 40.0

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

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 18068 KB Output isn't correct - L = 160
2 Incorrect 12 ms 18200 KB Output isn't correct - L = 160
3 Incorrect 16 ms 18200 KB Output isn't correct - L = 160
4 Incorrect 12 ms 18200 KB Output isn't correct - L = 160
5 Incorrect 16 ms 16616 KB Output isn't correct - L = 160
6 Incorrect 19 ms 16484 KB Output isn't correct - L = 160
7 Incorrect 22 ms 16484 KB Output isn't correct - L = 160
8 Incorrect 22 ms 16484 KB Output isn't correct - L = 160
9 Incorrect 6 ms 15692 KB Output isn't correct - L = 160
10 Incorrect 12 ms 15692 KB Output isn't correct - L = 160
11 Incorrect 6 ms 15692 KB Output isn't correct - L = 160
12 Incorrect 16 ms 16616 KB Output isn't correct - L = 160
13 Incorrect 576 ms 21704 KB Output isn't correct - L = 160
14 Incorrect 15 ms 16616 KB Output isn't correct - L = 160
15 Incorrect 15 ms 16616 KB Output isn't correct - L = 160
16 Incorrect 35 ms 16880 KB Output isn't correct - L = 160
17 Incorrect 42 ms 16880 KB Output isn't correct - L = 160
18 Incorrect 65 ms 16880 KB Output isn't correct - L = 160
19 Incorrect 9 ms 16088 KB Output isn't correct - L = 160
20 Incorrect 52 ms 16352 KB Output isn't correct - L = 160
21 Incorrect 95 ms 17276 KB Output isn't correct - L = 160
22 Incorrect 6 ms 15692 KB Output isn't correct - L = 160
23 Incorrect 9 ms 15692 KB Output isn't correct - L = 160
24 Incorrect 15 ms 15692 KB Output isn't correct - L = 160