oj.uz

Submission #1021010

# Submission time Handle Problem Language Result Execution time Memory
1021010 2024-07-12T12:50:44 Z EkinOnal Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 331 ms 64556 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++)
	{
		int a = edges[i][0], b = edges[i][1], c = l[i];
		adj[b].pb({a,c}); adj[a].pb({b,c});
	}

	priority_queue<pii,vector<pii>,greater<pii>> pq;
	vector<priority_queue<int>> dp(n);
	vi vis(n);

	for(int i=0;i<k;i++)
	{
		pq.push({0,entry[i]});
		vis[entry[i]]++;
		dp[entry[i]].push(0); dp[entry[i]].push(0);
	}
	
	while(pq.size())
	{
		int node = pq.top().s, cost=pq.top().f;
		pq.pop();
		if(vis[node]>1) continue;
		vis[node]++;
		if(vis[node]!=2) continue;
		if(node==0) return cost;

		//if(cost != )
		for (auto child : adj[node]) {
            int ch = child.f, wt = child.s;
            if (dp[ch].size() == 2) {
               // sort (all(dp[ch]));
                if (cost+wt < dp[ch].top()) {
                    dp[ch].pop();
                    dp[ch].push(cost+wt);
                    pq.push({cost+wt, ch});
                }
            }
            else {
                dp[ch].push(cost+wt);
                pq.push({cost+wt, ch});
            }
        }
	}
	
	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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4532 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4532 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 4700 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 2 ms 4440 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4532 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 4700 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 2 ms 4440 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct
16 Correct 291 ms 58568 KB Output is correct
17 Correct 72 ms 21360 KB Output is correct
18 Correct 64 ms 21072 KB Output is correct
19 Correct 331 ms 64556 KB Output is correct
20 Correct 200 ms 47648 KB Output is correct
21 Correct 33 ms 10864 KB Output is correct
22 Correct 266 ms 47800 KB Output is correct