Submission #849138

#	Time	Username	Problem	Language	Result	Execution time	Memory
849138		Hyojin	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	352 ms	65296 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
#define bit(n,i) ((n>>i)&1) 
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii> 
#define fi first
#define se second
#define ll long long
#define debug(x) cerr << #x << ' ' << x << '\n'
#define dbg(x) cerr<<#x<<' '<<x<<' '
const int base=31;
const int MOD=1e9+7;
const int N=1e5+5;
void setIO(const string &NAME)
{
	if (NAME.size())
	{
		freopen((NAME+".inp").c_str(),"r",stdin);
		freopen((NAME+".out").c_str(),"w",stdout);
	}
}
pair<ll,ll>d[N];
bool vis[N];
vector<pii>adj[N];
priority_queue<pair<ll,int>>pq;
ll travel_plan(int n,int m,int r[][2],int l[],int k,int p[])
{
	for (int i=0;i<m;i++)
	{
		int u=r[i][0],v=r[i][1];
		adj[u].pb({v,l[i]});
		adj[v].pb({u,l[i]});
	}
	for (int i=0;i<n;i++) d[i]={1e18,1e18};	
	for (int i=0;i<k;i++)
	{
		pq.push({0,p[i]});
		d[p[i]]={0,0};
	}
	while (pq.size())
	{
		auto [cost,u]=pq.top();
		cost=-cost;
		pq.pop();
		if (vis[u]) continue;
		vis[u]=1;
		for (int i=0;i<adj[u].size();i++)
		{
			int v=adj[u][i].fi,w=adj[u][i].se;
			if (cost+w<d[v].se)
			{
				d[v].se=cost+w;
				if (d[v].se<d[v].fi) swap(d[v].fi,d[v].se);
				if (d[v].se!=1e18) pq.push({-d[v].se,v});
			}
		}
	}
	return d[0].se;
}

Compilation message (stderr)

crocodile.cpp: In function 'long long int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for (int i=0;i<adj[u].size();i++)
      |                ~^~~~~~~~~~~~~~
crocodile.cpp: In function 'void setIO(const string&)':
crocodile.cpp:21:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   freopen((NAME+".inp").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
crocodile.cpp:22:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   freopen((NAME+".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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