답안 #69204 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69204	2018-08-20T09:20:36 Z	istlemin	Evacuation plan (IZhO18_plan)	C++14	23 / 100	2509 ms	84532 KB

plan

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	655 ms	69120 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 46.0

#	결과	실행 시간	메모리	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	-

답안 #69204

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 13.0 / 13.0

Subtask #3 0 / 12.0

Subtask #4 0 / 19.0

Subtask #5 0 / 46.0

Subtask #1
10.0 / 10.0

Subtask #2
13.0 / 13.0

Subtask #3
0 / 12.0

Subtask #4
0 / 19.0

Subtask #5
0 / 46.0