Submission #391123

#	Time	Username	Problem	Language	Result	Execution time	Memory
391123		arwaeystoamneg	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	648 ms	44808 KiB

crocodile

// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
}
#include "crocodile.h"
struct T
{
	int a, b;
	int insert(int c)
	{
		if (c < a)
		{
			b = a;
			a = c;
			return 1;
		}
		else if (c < b)
		{
			b = c;
			return 1;
		}
		return 0;
	}
	int get()
	{
		return b;
	}
};
const int MAX = 1e5 + 5;
int n, start[MAX];
vpi adj[MAX];
T dist[MAX];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	n = N;
	F0R(i, M)
	{
		adj[R[i][0]].pb({ R[i][1],L[i] });
		adj[R[i][1]].pb({ R[i][0],L[i] });
	}
	F0R(i, K)start[i] = P[i];
	F0R(i, n)dist[i] = { inf,inf };
	priority_queue<pii, vpi, greater<pii>>todo;
	F0R(i, K)
	{
		dist[start[i]] = { 0,0 };
		todo.push({ 0,start[i] });
	}
	bitset<MAX>v;
	while (sz(todo))
	{
		pll t = todo.top();
		todo.pop();
		if (dist[t.s].get() != t.f || v[t.s])continue;
		v[t.s] = 1;
		ll d = dist[t.s].get();
		trav(x, adj[t.s])
		{
			if (v[x.f])continue;
			if (dist[x.f].insert(x.s + d))
			{
				if (dist[x.f].get() != inf)
				{
					todo.push({ dist[x.f].get(),x.f });
				}
			}
		}
	}
	assert(dist[0].get() != linf);
	return dist[0].get();
}

#ifdef arwaeystoamneg

#define MAX_N 50000
#define MAX_M 10000000

static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

inline
void my_assert(int e) { if (!e) abort(); }

void read_input()
{
	int i;
	my_assert(3 == scanf("%d %d %d", &N, &M, &K));
	for (i = 0; i < M; i++)
		my_assert(3 == scanf("%d %d %d", &R[i][0], &R[i][1], &L[i]));
	for (i = 0; i < K; i++)
		my_assert(1 == scanf("%d", &P[i]));
	my_assert(1 == scanf("%d", &solution));
}

int main()
{
	setIO("test1");
	int ans;
	read_input();
	ans = travel_plan(N, M, R, L, K, P);
	if (ans == solution)
		printf("Correct.\n");
	else
		printf("Incorrect. Returned %d, Expected %d.\n", ans, solution);

	return 0;
}

#endif

Compilation message (stderr)

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

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11