oj.uz

Submission #69204

# Submission time Handle Problem Language Result Execution time Memory
69204 2018-08-20T09:20:36 Z istlemin Evacuation plan (IZhO18_plan) C++14
23 / 100
 2509 ms 84532 KB 
#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

class UnionFind{
public:
	vi p,r;
	UnionFind(ll n){
        p.resize(n);
        rep(i,0,n) p[i] = i;
        r.resize(n,1);
	}

    ll find(ll a){
		return p[a]==a?a:p[a]=find(p[a]);
    }

    void join(ll a,ll b){
        a = find(a);
        b = find(b);

        if(r[a]>r[b]){
            p[b] = a;
        } else if(r[b]>r[a]){
			p[a] = b;
        } else {
            p[a] = b;
            r[b]++;
        }
    }
};

ll n,k;
vector<vector<pii>> ge;
vi g;

vi dist;

void getDists(){
	dist.resize(n,-1);
    set<pii> q;
    rep(i,0,k) q.emplace(0,g[i]);
    while(q.size()){
        ll v = q.begin()->second;
        ll d = q.begin()->first;
        q.erase(q.begin());
		if(dist[v]!=-1) continue;
		dist[v] = d;

		rep(i,0,ge[v].size()){
			q.emplace(d+ge[v][i].second,ge[v][i].first);
		}
    }
}

vector<vector<pii>> e;

void makeTree(){
    vector<tuple<ll,ll,ll> > edges;
    rep(i,0,n){
		rep(j,0,ge[i].size()){
			edges.emplace_back(min(dist[ge[i][j].first],dist[i]),i,ge[i][j].first);
		}
    }
    sort(all(edges));
    reverse(all(edges));

    UnionFind uf(n);
    e.resize(n);
    rep(i,0,edges.size()){
		ll a,b,w;
		tie(w,a,b) = edges[i];
        if(uf.find(a)!=uf.find(b)){
            uf.join(a,b);
			e[a].emplace_back(b,w);
			e[b].emplace_back(a,w);
        }
    }
}

class LCA {
public:
    vi levels;
    vector<vector<pii> > jump;

	LCA(){
		jump.resize(30,vector<pii>(n));
        levels.resize(n);
        dfs(0,0,0,1e18);

        rep(i,1,30){
			rep(j,0,n){
				jump[i][j].first = jump[i-1][jump[i-1][j].first].first;
				jump[i][j].second = min(jump[i-1][j].second,jump[i-1][jump[i-1][j].first].second);
			}
        }
	}

    void dfs(ll v,ll last,ll level,ll w){
        jump[0][v] = {last,w};
        levels[v] = level;
		rep(i,0,e[v].size()){
			if(e[v][i].first==last) continue;
			dfs(e[v][i].first,v,level+1,e[v][i].second);
		}
    }

    ll getMin(ll a,ll b){
        ll mn = 1e18;
        if(levels[a]<levels[b]) swap(a,b);
        for(int i = 29; i>=0;--i){
            if(levels[jump[i][a].first]>=levels[b]){
				mn = min(mn,jump[i][a].second);
				a = jump[i][a].first;
            }
        }
        assert(levels[a]==levels[b]);
        if(a==b) return mn;

        for(int i = 29; i>=0;--i){
            if(jump[i][a].first!=jump[i][a].first){
				mn = min(mn,jump[i][a].second);
				a = jump[i][a].first;
				mn = min(mn,jump[i][b].second);
				b = jump[i][b].first;
            }
        }
        //assert(a!=b);
		mn = min(mn,jump[0][a].second);
		a = jump[0][a].first;
		mn = min(mn,jump[0][b].second);
		b = jump[0][b].first;
		//assert(a==b);
		return mn;



    }
};

int main(){
	cin.sync_with_stdio(false);
    ll m;
    cin>>n>>m;
    ge.resize(n);
    rep(i,0,m){
		ll a,b,w;
		cin>>a>>b>>w;
		--a;--b;
        ge[a].emplace_back(b,w);
        ge[b].emplace_back(a,w);
    }
    cin>>k;
    g.resize(k);
    rep(i,0,k) {
		cin>>g[i];
		--g[i];
	}
	getDists();
    //rep(i,0,n) cout<<i+1<<": "<<dist[i]<<endl;
	makeTree();
	/*cout<<"tree"<<endl;
    rep(i,0,n){
		cout<<i+1<<": ";
		rep(j,0,e[i].size()){
			cout<<e[i][j].first+1<<" ";
		}
		cout<<endl;
    }*/

    LCA* lca = new LCA();

    ll q;
    cin>>q;
    rep(i,0,q){
		ll a,b;
		cin>>a>>b;
		--a; --b;
        cout<<lca->getMin(a,b)<<endl;
    }
    _Exit(0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 6 ms 1020 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 7 ms 1016 KB Output is correct
6 Correct 7 ms 1016 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 7 ms 1016 KB Output is correct
10 Correct 7 ms 1016 KB Output is correct
11 Correct 7 ms 1016 KB Output is correct
12 Correct 5 ms 1016 KB Output is correct
13 Correct 7 ms 1044 KB Output is correct
14 Correct 7 ms 1016 KB Output is correct
15 Correct 7 ms 1016 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 6 ms 1020 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 7 ms 1016 KB Output is correct
6 Correct 7 ms 1016 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 7 ms 1016 KB Output is correct
10 Correct 7 ms 1016 KB Output is correct
11 Correct 7 ms 1016 KB Output is correct
12 Correct 5 ms 1016 KB Output is correct
13 Correct 7 ms 1044 KB Output is correct
14 Correct 7 ms 1016 KB Output is correct
15 Correct 7 ms 1016 KB Output is correct
16 Correct 687 ms 53744 KB Output is correct
17 Correct 2405 ms 84532 KB Output is correct
18 Correct 118 ms 10108 KB Output is correct
19 Correct 593 ms 66564 KB Output is correct
20 Correct 2407 ms 84268 KB Output is correct
21 Correct 1078 ms 70748 KB Output is correct
22 Correct 579 ms 70064 KB Output is correct
23 Correct 2413 ms 84152 KB Output is correct
24 Correct 2406 ms 83984 KB Output is correct
25 Correct 2509 ms 84064 KB Output is correct
26 Correct 603 ms 66144 KB Output is correct
27 Correct 622 ms 66436 KB Output is correct
28 Correct 597 ms 66228 KB Output is correct
29 Correct 596 ms 66492 KB Output is correct
30 Correct 597 ms 66648 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 655 ms 69120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 1016 KB Output is correct
3 Correct 6 ms 1020 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 7 ms 1016 KB Output is correct
6 Correct 7 ms 1016 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 7 ms 1016 KB Output is correct
10 Correct 7 ms 1016 KB Output is correct
11 Correct 7 ms 1016 KB Output is correct
12 Correct 5 ms 1016 KB Output is correct
13 Correct 7 ms 1044 KB Output is correct
14 Correct 7 ms 1016 KB Output is correct
15 Correct 7 ms 1016 KB Output is correct
16 Correct 687 ms 53744 KB Output is correct
17 Correct 2405 ms 84532 KB Output is correct
18 Correct 118 ms 10108 KB Output is correct
19 Correct 593 ms 66564 KB Output is correct
20 Correct 2407 ms 84268 KB Output is correct
21 Correct 1078 ms 70748 KB Output is correct
22 Correct 579 ms 70064 KB Output is correct
23 Correct 2413 ms 84152 KB Output is correct
24 Correct 2406 ms 83984 KB Output is correct
25 Correct 2509 ms 84064 KB Output is correct
26 Correct 603 ms 66144 KB Output is correct
27 Correct 622 ms 66436 KB Output is correct
28 Correct 597 ms 66228 KB Output is correct
29 Correct 596 ms 66492 KB Output is correct
30 Correct 597 ms 66648 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Incorrect 2 ms 380 KB Output isn't correct
33 Halted 0 ms 0 KB -