oj.uz

Submission #860942

# Submission time Handle Problem Language Result Execution time Memory
860942 2023-10-14T21:13:38 Z Huseyn123 Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 739 ms 66976 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#define MAX 100001
#define INF INT_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
    for(int i=0;i<b;i++){\
        cin >> a[i];\
    }\
}
#define inputvec(a,b){\
    for(int i=0;i<b;i++){\
        ll num;\
        cin >> num;\
        a.pb(num);\
    }\
}
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << "\n";\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << x << " ";\
    }\
    cout << "\n";\
}
#define reset(a,n,v){\
    for(int i=0;i<n;i++){\
        a[i]=v;\
    }\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
vector<vector<pii>> g;
int dist[MAX];
int a1[MAX],b1[MAX];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
	g.resize(N); 
	for(int i=0;i<N;i++){
		dist[i]=INF;
	}
	for(int i=0;i<M;i++){
		g[R[i][0]].pb(mp(R[i][1],L[i])); 
		g[R[i][1]].pb(mp(R[i][0],L[i]));
	}
	for(int i=0;i<K;i++){
		dist[P[i]]=0;
	}
	set<pll> a; 
	for(int i=0;i<N;i++){
		if(dist[i]==0){
			continue;
		}
		ll h=INF,h1=INF;
		for(auto x:g[i]){
			if(dist[x.ff]==0){
				if(x.ss<h){
					h1=min(h1,h);
					h=x.ss; 
				}
				else if(x.ss<h1){
					h1=x.ss; 
				}
			}
		}
		a1[i]=h; 
		b1[i]=h1;
		a.ins(mp(h1,i));
	}
	for(int i=0;i<N-K;i++){
		auto it=a.begin(); 
		pll t=*it; 
		a.erase(t);
		//cout << gett(t,0) << " " << gett(t,1) << " " << gett(t,2) << "\n";
		dist[t.ss]=t.ff;
		for(auto x:g[t.ss]){
			if(dist[x.ff]!=INF){
				continue;
			}
			a.erase(mp(b1[x.ff],x.ff));
			if(x.ss+dist[t.ss]<a1[x.ff]){
				b1[x.ff]=min(b1[x.ff],a1[x.ff]);
				a1[x.ff]=x.ss+dist[t.ss]; 
			}
			else if(x.ss+dist[t.ss]<b1[x.ff]){
				b1[x.ff]=x.ss+dist[t.ss]; 
			}
			a.ins(mp(b1[x.ff],x.ff));
		}
		if(t.ss==0){
			break;
		}
	}
	return dist[0];
}

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 4444 KB Output is correct
3 Correct 1 ms 4544 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 4560 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 4444 KB Output is correct
3 Correct 1 ms 4544 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 4560 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4556 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 4 ms 4700 KB Output is correct
13 Correct 3 ms 4896 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4544 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 4560 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4556 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 4 ms 4700 KB Output is correct
13 Correct 3 ms 4896 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 731 ms 59328 KB Output is correct
17 Correct 98 ms 23308 KB Output is correct
18 Correct 102 ms 24472 KB Output is correct
19 Correct 739 ms 66976 KB Output is correct
20 Correct 215 ms 52008 KB Output is correct
21 Correct 48 ms 10832 KB Output is correct
22 Correct 380 ms 51796 KB Output is correct