oj.uz

답안 #1021014

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1021014 2024-07-12T12:53:41 Z EkinOnal 악어의 지하 도시 (IOI11_crocodile) C++17
100 / 100
 307 ms 47824 KB 
//#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
//#include <cstdio>
//#include <iostream>
using namespace std;
 
#define MAX 100007
#define pb push_back
//#define mp make_pair 
//#define int long long
#define f first
#define s second
#define vi vector<int>
#define pii pair<int,int>
#define si set<int>
#define vpii vector<pair<int,int>> 
const int mod = 1e9+7;
//const int INF = 1e18;
// myMap.begin()->first :  key
// myMap.begin()->second : value
 
int epow(int a,int b){int ans=1;while(b){if(b&1) ans*=a;a*=a;ans%=mod;a%=mod;b>>=1;}return ans%mod;}
int gcd(int a,int b) {if(a<b)swap(a,b);while(b){int tmp=b;b=a%b;a=tmp;}return a;}
int mul(int a,int b){return ((a%mod)*(b%mod))%mod;}
 
 
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
 
#define N 50
 
 
 
int solve(int n, int m, int (*edges)[2], int* l, int k, int *entry) 
{	
 
	vector<pii> adj[n+5];
	for(int i=0;i<m;i++)
	{
		adj[edges[i][1]].pb({edges[i][0],l[i]}); adj[edges[i][0]].pb({edges[i][1],l[i]});
	}
 
	vi exits(k);
	for(int i=0;i<k;i++) exits[i]=entry[i];
 
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	vector<priority_queue<int>> dp(n+2);
	vi vis(n+2);
 
	for(int i=0;i<k;i++)
	{
		pq.push({0,exits[i]});
		vis[exits[i]]=1;
		dp[exits[i]].push(0LL); dp[exits[i]].push(0LL);
	}
	
	while(pq.size())
	{
		int node = pq.top().s, cost=pq.top().f;
		pq.pop();
		if(vis[node]>1) continue;
	//	if(vis[node]++) continue;
		vis[node]++;
		if(vis[node]!=2) continue;
		if(node==0LL) return cost;
 
		//if(cost != )
		for(auto u : adj[node])
		{
			if(dp[u.f].size()<2)
			{
				dp[u.f].push(cost+u.s);
				pq.push({cost+u.s,u.f});
			}
			else if(dp[u.f].top() > cost+u.s)
			{
				dp[u.f].pop(); dp[u.f].push(cost+u.s);
				pq.push({cost+u.s,u.f});
			}
		}
	}
	
	cout << "BAD\n";
	
	
    return -1;
}	
 
 
 
int travel_plan(int n, int m, int (*r)[2], int* l, int k, int *p) {
    return solve(n, m, r, l, k, p);
}

Subtask #1
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct

Subtask #2
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4696 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct
13 Correct 3 ms 4700 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4696 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct
13 Correct 3 ms 4700 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 307 ms 42184 KB Output is correct
17 Correct 69 ms 18004 KB Output is correct
18 Correct 60 ms 17488 KB Output is correct
19 Correct 276 ms 47824 KB Output is correct
20 Correct 165 ms 34384 KB Output is correct
21 Correct 26 ms 9296 KB Output is correct
22 Correct 199 ms 32180 KB Output is correct