oj.uz

Submission #131946

# Submission time Handle Problem Language Result Execution time Memory
131946 2019-07-18T05:28:39 Z 이온조(#3189) Wild Boar (JOI18_wild_boar) C++14
12 / 100
 7 ms 1656 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

struct info {
	int v, p, x, i;
};

bool operator <(info PP, info QQ) {
	return PP.v > QQ.v;
}

int N, M, T, L;
vector<pii> adj[2009];
int X[100009], P[100009], Q[100009];
int D[11][11][100009];

int main() {
 	scanf("%d%d%d%d",&N,&M,&T,&L);
	for(int i=0; i<M; i++) {
		int u, v, w; scanf("%d%d%d",&u,&v,&w);
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	for(int i=1; i<=L; i++) scanf("%d",&X[i]);
	for(int i=1; i<=T; i++) scanf("%d%d",&P[i],&Q[i]);
	if(T == 1) {
		X[P[1]] = Q[1];
		for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) for(int k=1; k<=L; k++) D[i][j][k] = 1e9;
		priority_queue<info> pq; pq.push({0, X[1], X[1], 1});
		D[X[1]][X[1]][1] = 0;
		int ans = 1e9;
		while(pq.size()) {
			info n = pq.top(); pq.pop();
			if(n.v != D[n.p][n.x][n.i]) continue;
			if(n.i == L) ans = min(ans, n.v);
			for(auto& it: adj[n.x]) {
				int &th = D[n.x][it.first][n.i + (it.first == X[n.i+1])];
				if(th > n.v + it.second && it.first != n.p) {
					th = n.v + it.second;
					pq.push({th, n.x, it.first, n.i + (it.first == X[n.i+1])});
				}
			}
		}
		if(ans == 1e9) puts("-1");
		else printf("%d", ans);
	}
	else assert(0);
	return 0;
}

Compilation message

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d",&N,&M,&T,&L);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:22:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v, w; scanf("%d%d%d",&u,&v,&w);
                ~~~~~^~~~~~~~~~~~~~~~~~~
wild_boar.cpp:26:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=L; i++) scanf("%d",&X[i]);
                          ~~~~~^~~~~~~~~~~~
wild_boar.cpp:27:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=T; i++) scanf("%d%d",&P[i],&Q[i]);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 2 ms 760 KB Output is correct
15 Correct 2 ms 888 KB Output is correct
16 Correct 2 ms 760 KB Output is correct
17 Correct 2 ms 764 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Correct 2 ms 888 KB Output is correct
20 Correct 2 ms 888 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 3 ms 504 KB Output is correct
23 Correct 2 ms 504 KB Output is correct
24 Correct 2 ms 504 KB Output is correct
25 Correct 3 ms 504 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 2 ms 760 KB Output is correct
15 Correct 2 ms 888 KB Output is correct
16 Correct 2 ms 760 KB Output is correct
17 Correct 2 ms 764 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Correct 2 ms 888 KB Output is correct
20 Correct 2 ms 888 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 3 ms 504 KB Output is correct
23 Correct 2 ms 504 KB Output is correct
24 Correct 2 ms 504 KB Output is correct
25 Correct 3 ms 504 KB Output is correct
26 Runtime error 7 ms 1656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 2 ms 760 KB Output is correct
15 Correct 2 ms 888 KB Output is correct
16 Correct 2 ms 760 KB Output is correct
17 Correct 2 ms 764 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Correct 2 ms 888 KB Output is correct
20 Correct 2 ms 888 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 3 ms 504 KB Output is correct
23 Correct 2 ms 504 KB Output is correct
24 Correct 2 ms 504 KB Output is correct
25 Correct 3 ms 504 KB Output is correct
26 Runtime error 7 ms 1656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 2 ms 760 KB Output is correct
15 Correct 2 ms 888 KB Output is correct
16 Correct 2 ms 760 KB Output is correct
17 Correct 2 ms 764 KB Output is correct
18 Correct 2 ms 760 KB Output is correct
19 Correct 2 ms 888 KB Output is correct
20 Correct 2 ms 888 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 3 ms 504 KB Output is correct
23 Correct 2 ms 504 KB Output is correct
24 Correct 2 ms 504 KB Output is correct
25 Correct 3 ms 504 KB Output is correct
26 Runtime error 7 ms 1656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Halted 0 ms 0 KB -