oj.uz

답안 #671703

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
671703 2022-12-13T15:21:18 Z smartmonky Money (IZhO17_money) C++14
0 / 100
 1500 ms 8148 KB 
#include <bits/stdc++.h>
  
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
using namespace std;
 
const int N = 1e5 + 10;
int d[N], ans[N], par[N], sz[N];
vector < pair <int,int> > g[N];
set <int> s[N];
int n;
int vis[N];
int find(int a){
    if(par[a] == a)
        return a;
    return par[a] = find(par[a]);
}
void connect(int a, int b, int w){
    a = find(a);
    b = find(b);
    if(a == b)return;
	par[b] = a;
	sz[b] += sz[a];
    if ((int) s[a].size() > (int) s[b].size()) swap(s[a] , s[b]);
 
    for (auto x : s[b])
    {
        if (s[a].find(x) != s[a].end())
        {
            ans[x] = w;
            s[a].erase(x);
        }
        else
        {
            s[a].insert(x);
        }
    }
}
main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(d, 0x3f3f3f, sizeof(d));
	int m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		par[i] = i;
		sz[i] = 1;
	}
	for(int i = 0; i < m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		g[a].pb({b, c});
		g[b].pb({a, c});
	}
	int k;
	cin >> k;
	set <pair <int,int> > st;
	for(int i = 0; i < k; i++){
		int a;
		cin >> a;
		st.insert({0, a});
		d[a] = 0;
	}
	while (!st.empty()){
		int v = st.begin()->second;
		st.erase (st.begin());
		for (size_t j=0; j<g[v].size(); ++j) {
			int to = g[v][j].first,
				len = g[v][j].second;
			if (d[v] + len < d[to]) {
				st.erase (make_pair (d[to], to));
				d[to] = d[v] + len;
				st.insert (make_pair (d[to], to));
			}
		}
	}
	vector <pair <int,int> > vp;
	for(int i = 1; i <= n; i++){
		vp.pb({d[i], i});
	}
	int q;
	cin >> q;
	for(int i = 1; i <= q; i++){
		int a, b;
		cin >> a >> b;
		s[a].insert(i);
		s[b].insert(i);
	}
	sort(rall(vp));
	for (auto x : vp){
        int w = x.first , u = x.second;
        vis[u] = 1;
        for (auto adj : g[u])
        {
            int v = adj.ff;
            if (vis[v]) 
				connect(u , v , w);
        }
    }
	for(int i = 1; i <= q; i++)cout << ans[i] << endl;
}

Compilation message

money.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main(){
      | ^~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1583 ms 8148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1583 ms 8148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1583 ms 8148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1583 ms 8148 KB Time limit exceeded
2 Halted 0 ms 0 KB -