oj.uz

Submission #367226

# Submission time Handle Problem Language Result Execution time Memory
367226 2021-02-16T16:06:56 Z Sparky_09 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 634 ms 61604 KB 
#include "crocodile.h"
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;

template <class T>
void rd(T &x) {
	int sgn = 1;
	char ch;
	x = 0;
	for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar()) ;
	if (ch == '-') ch = getchar(), sgn = -1;
	for (; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	x *= sgn;
}
template <class T>
void wr(T x) {
	if (x < 0) putchar('-'), wr(-x);
	else if (x < 10) putchar(x + '0');
	else wr(x / 10), putchar(x % 10 + '0');
}
void usaco(string s){
  freopen((s+".in").c_str(), "r", stdin);
  freopen((s+".out").c_str(), "w", stdout);
}

const int mxn = 100005;
int n, m, vis[mxn], dist[mxn][2];
vector<pair<int,int>> adj[mxn];
priority_queue<pair<int,int>> pq;


int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
  n=N;m=M;
  rep(i,0,m){
    adj[R[i][0]+1].emplace_back(L[i],R[i][1]+1);
		adj[R[i][1]+1].emplace_back(L[i],R[i][0]+1);
  }
  memset(dist, 0x3f, sizeof dist);
  rep(i,0,K){
		dist[P[i]+1][0] = dist[P[i]+1][1] = 0;
		vis[P[i]+1] = 1;
		pq.push({0,P[i]+1});
	}
	while(vis[1]!=2){
    int cost = -pq.top().first;
    int nod = pq.top().second; pq.pop();
		if(vis[nod]==2)	continue;
		if(vis[nod]==1){
			if(nod==1)	return cost;
			vis[nod] = 2;
			for(auto i: adj[nod]){
				int c = i.first, b = i.second;
				if(vis[b] != 2 && cost+c < dist[b][1]){
					dist[b][1] = cost+c;
					if(dist[b][1] < dist[b][0])	swap(dist[b][1] , dist[b][0]);
					pq.push({-(cost+c), b});
				}
			}
		}
		else	vis[nod] = 1;
	}
	return -1;
 
}

/*
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif

}
*/

Compilation message

crocodile.cpp: In function 'void usaco(std::string)':
crocodile.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   30 |   freopen((s+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
crocodile.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   31 |   freopen((s+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3584 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 3 ms 3436 KB Output is correct
4 Correct 3 ms 3564 KB Output is correct
5 Correct 3 ms 3564 KB Output is correct
6 Correct 3 ms 3564 KB Output is correct
7 Correct 3 ms 3564 KB Output is correct
8 Correct 3 ms 3564 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3584 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 3 ms 3436 KB Output is correct
4 Correct 3 ms 3564 KB Output is correct
5 Correct 3 ms 3564 KB Output is correct
6 Correct 3 ms 3564 KB Output is correct
7 Correct 3 ms 3564 KB Output is correct
8 Correct 3 ms 3564 KB Output is correct
9 Correct 4 ms 3692 KB Output is correct
10 Correct 3 ms 3436 KB Output is correct
11 Correct 3 ms 3564 KB Output is correct
12 Correct 6 ms 3948 KB Output is correct
13 Correct 6 ms 4096 KB Output is correct
14 Correct 3 ms 3564 KB Output is correct
15 Correct 3 ms 3584 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3584 KB Output is correct
2 Correct 2 ms 3436 KB Output is correct
3 Correct 3 ms 3436 KB Output is correct
4 Correct 3 ms 3564 KB Output is correct
5 Correct 3 ms 3564 KB Output is correct
6 Correct 3 ms 3564 KB Output is correct
7 Correct 3 ms 3564 KB Output is correct
8 Correct 3 ms 3564 KB Output is correct
9 Correct 4 ms 3692 KB Output is correct
10 Correct 3 ms 3436 KB Output is correct
11 Correct 3 ms 3564 KB Output is correct
12 Correct 6 ms 3948 KB Output is correct
13 Correct 6 ms 4096 KB Output is correct
14 Correct 3 ms 3564 KB Output is correct
15 Correct 3 ms 3584 KB Output is correct
16 Correct 544 ms 59140 KB Output is correct
17 Correct 88 ms 14188 KB Output is correct
18 Correct 97 ms 15684 KB Output is correct
19 Correct 634 ms 61604 KB Output is correct
20 Correct 322 ms 50284 KB Output is correct
21 Correct 43 ms 8428 KB Output is correct
22 Correct 361 ms 46700 KB Output is correct