Submission #885302

#	Time	Username	Problem	Language	Result	Execution time	Memory
885302		Elvin_Fritl	Evacuation plan (IZhO18_plan)	C++17	19 / 100	661 ms	41728 KiB

plan

#include <bits/stdc++.h>
using namespace std;
 
#define io                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
 
 
typedef long long ll;
 
ll bp(ll n,ll m){
    if(m == 0){
        return 1;
    }
    if(m == 1){
        return n;
    }
    if(m%2==0){
        return bp(n*n,m/2);
    }
    return n*bp(n,m-1);
}
 
 
const int N =  2e5 + 545, M = 33, inf = 1e9 + 99 , mod = 1e9 + 7;
const ll inff = 1e12;
 
vector<int> l(N) , r(N) , mid(N) , dp(N , inf) , par(N , -1) , sz(N , 1);
 
bool cmp(int a,int b) {
	return mid[a] > mid[b];
}
 
bool cmp2(int a,int b) {
	return dp[a] > dp[b];
}
 
int union_find(int s){
    if(par[s] == -1) {
		return s;
	}
    return par[s] = union_find(par[s]);
}
 
void union_set(int u, int v){
    u = union_find(u);
    v = union_find(v);
    if(u == v) {
		return;
	}
    if(sz[u] < sz[v]) {
		swap(u, v);
	}
    sz[u] += sz[v];
    par[v] = u;
}
 
int main()
{
	io;
	
	int n,m;
	cin >> n >> m;
	vector<pair<int , int>>g1[n + 1];
	vector<int> g2[n + 1];
	for(int i=0;i<m;i++) {
		int u,v,w;
		cin >> u >> v >> w;
		g1[u].push_back({v , w});
		g1[v].push_back({u , w});
		g2[u].push_back(v);
		g2[v].push_back(u);
	}
	priority_queue<pair<int , int>> q;
	int k;
	cin >> k;
	for(int i=0;i<k;i++) {
		int u;
		cin >> u;
		dp[u] = 0;
		q.push({0 , u});
	}
	while(q.size() > 0) {
		int fi = q.top().first , se = q.top().second;
		q.pop();
		for(auto &i : g1[se]) {
			if(dp[i.first] > i.second + dp[se]) {
				dp[i.first] = dp[se] + i.second;
				q.push({-dp[i.first] , i.first});
			}
		}
	}
	int Q;
	cin >> Q;
	vector<int> x(Q + 1 , -1) , t(Q + 1 , -1) , ind(n + 1 , -1) , ind2(Q + 1 , -1) , color(n + 1 , 0);
	dp[0] = inf;
	for(int i=1;i<=n;i++) {
		ind[i] = i;
	}
	cerr << "true\n";
	sort(ind.begin() + 1, ind.end() , cmp2);
	cerr << "true\n";
	for(int i=1;i<=Q;i++) {
		 cin >> x[i] >> t[i];
		 l[i] = 0;
		 r[i] = 1e8;
	 }
	 for(int mask=0;mask<=31;mask++) {
		 for(int i=1;i<=Q;i++) {
			 mid[i] = (l[i] + r[i])/2;
			 ind2[i] = i;
		 }
		 for(int i=1;i<=n;i++) {
			 sz[i] = 1;
			 par[i] = -1;
			 color[i] = 0;
		 }
		 sort(ind2.begin() + 1 , ind2.end() , cmp);
		 int j=1;
		 vector<int> color(n + 1 , 0);
		 for(int i=1;i<=Q;i++) {
			 while(j <= n && dp[ind[j]] >= mid[ind2[i]]) {
				 for(auto &u : g2[ind[j]]) { 
					 if(color[u] == 1 || dp[u] < mid[ind2[i]]) {
						 continue;
					 }
					 union_set(u , ind[j]);
				 }
				 color[ind[j]] = 1;
				 j++;
			 } 
			 if(union_find(x[ind2[i]]) == union_find(t[ind2[i]])) {
				 l[ind2[i]] = mid[ind2[i]] + 1;
			 }
			 else {
				 r[ind2[i]] = mid[ind2[i]] - 1;
			 }
		 }
	 }
	 for(int i=1;i<=Q;i++) {
		 cout << mid[i] << " ";
	 }
	 cout << endl;
	
    return 0;
 
}
/*
 
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
 
*/

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:85:7: warning: unused variable 'fi' [-Wunused-variable]
   85 |   int fi = q.top().first , se = q.top().second;
      |       ^~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 19 / 19
• Subtask 5: 0 / 46