oj.uz

Submission #89896

# Submission time Handle Problem Language Result Execution time Memory
89896 2018-12-18T19:42:07 Z Abelyan Evacuation plan (IZhO18_plan) C++14
100 / 100
 1217 ms 96316 KB 
#include <bits/stdc++.h>
using namespace std;

const int N=500005;
const int LG=log2(N)+3;

#define fr first
#define sc second

int l;
int anc[N][LG];
int in[N],out[N],timer;

void dfs(int v,vector<int>* g,int par=0){
    //cout<<v<<endl;
    in[v]=timer++;
    anc[v][0]=par;
    for (int i=1;i<=l;i++){
        anc[v][i]=anc[anc[v][i-1]][i-1];
    }
    for (auto to:g[v]){
        if (to==par)continue;
        dfs(to,g,v);
    }
    out[v]=timer++;
}

bool is_anc(int a,int b){
    if (b==0 || a==b)return true;
    if (in[a]>in[b] && in[a]<out[b])return true;
    return false;
}

int lca(int a,int b){
    if (is_anc(a,b)) return b;
    if (is_anc(b,a)) return a;
    for (int i=l;i>=0;i--)
        if (!is_anc(b,anc[a][i]))
            a=anc[a][i];
    return anc[a][0];
}
void prec(int n,int root,vector<int>* g){
    l=0;
    while ((1<<l)<=n)l++;
    dfs(root,g);
}

vector<pair<int,int> > g[N];
vector<int> gr[N];
int dp[N],inComp[N],node[N],val[N];
bool col[N];
vector<int> comp[N];

int main(){
    ios_base::sync_with_stdio(false);
    //freopen("input.txt","r",stdin);
    int n,m;
    cin>>n>>m;
    for (int i=0;i<m;i++){
        int a,b,l;
        cin>>a>>b>>l;
        g[a].push_back({b,l});
        g[b].push_back({a,l});
    }
    for (int i=1;i<=n;i++){
        dp[i]=INT_MAX;
    }
    priority_queue<pair<int,int> > pq;
    int blackNum;
    cin>>blackNum;
    for (int i=0;i<blackNum;i++){
        int k;
        cin>>k;
        dp[k]=0;
        pq.push({0,k});
    }
    while (!pq.empty()){
        int cur;
        do{
            cur=pq.top().sc;
            pq.pop();
        }while(col[cur] && !pq.empty());
        if (col[cur])break;
        col[cur]=true;
        for (auto to:g[cur]){
            if (dp[cur]+to.sc<dp[to.fr]){
                dp[to.fr]=dp[cur]+to.sc;
                pq.push({-dp[to.fr],to.fr});
            }
        }
    }
    vector<pair<int,pair<int,int> > >v;
    for (int i=1;i<=n;i++){
        //cout<<dp[i]<<" ";
        inComp[i]=i;
        node[i]=i;
        comp[i].push_back(i);
        for (auto to:g[i]){
            v.push_back({-min(dp[to.fr],dp[i]),{i,to.fr}});
        }
    }
    //cout<<endl;
    sort(v.begin(),v.end());
    int cnt=n+1;
    for (int i=0;i<v.size();i++){
        int a=v[i].sc.fr,b=v[i].sc.sc,len=-v[i].fr;
        if (inComp[a]==inComp[b])continue;
        //cout<<a<<" "<<b<<" ";
        a=inComp[a];
        b=inComp[b];
        //cout<<a<<" "<<b<<endl;
        gr[cnt].push_back(node[a]);
        gr[cnt].push_back(node[b]);
        //cout<<cnt<<" "<<node[a]<<" "<<node[b]<<endl;
        if (comp[a].size()<comp[b].size())swap(a,b);
        for (auto tv:comp[b]){
            inComp[tv]=a;
            comp[a].push_back(tv);
        }
        val[cnt]=len;
        node[a]=cnt++;
    }
    prec(cnt-1,cnt-1,gr);
    int q;
    cin>>q;
    for (int i=0;i<q;i++){
        int a,b;
        cin>>a>>b;
        cout<<val[lca(a,b)]<<endl;
    }
    return 0;
}

Compilation message

plan.cpp: In function 'int main()':
plan.cpp:105:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v.size();i++){
                  ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 38 ms 35960 KB Output is correct
3 Correct 38 ms 35960 KB Output is correct
4 Correct 34 ms 35576 KB Output is correct
5 Correct 42 ms 36064 KB Output is correct
6 Correct 38 ms 35960 KB Output is correct
7 Correct 33 ms 35704 KB Output is correct
8 Correct 34 ms 35704 KB Output is correct
9 Correct 38 ms 35960 KB Output is correct
10 Correct 38 ms 35960 KB Output is correct
11 Correct 43 ms 35960 KB Output is correct
12 Correct 38 ms 35960 KB Output is correct
13 Correct 38 ms 35992 KB Output is correct
14 Correct 39 ms 35960 KB Output is correct
15 Correct 38 ms 35960 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 38 ms 35960 KB Output is correct
3 Correct 38 ms 35960 KB Output is correct
4 Correct 34 ms 35576 KB Output is correct
5 Correct 42 ms 36064 KB Output is correct
6 Correct 38 ms 35960 KB Output is correct
7 Correct 33 ms 35704 KB Output is correct
8 Correct 34 ms 35704 KB Output is correct
9 Correct 38 ms 35960 KB Output is correct
10 Correct 38 ms 35960 KB Output is correct
11 Correct 43 ms 35960 KB Output is correct
12 Correct 38 ms 35960 KB Output is correct
13 Correct 38 ms 35992 KB Output is correct
14 Correct 39 ms 35960 KB Output is correct
15 Correct 38 ms 35960 KB Output is correct
16 Correct 596 ms 65236 KB Output is correct
17 Correct 1149 ms 93400 KB Output is correct
18 Correct 112 ms 41708 KB Output is correct
19 Correct 586 ms 75752 KB Output is correct
20 Correct 1130 ms 93388 KB Output is correct
21 Correct 787 ms 78032 KB Output is correct
22 Correct 617 ms 74648 KB Output is correct
23 Correct 1147 ms 93480 KB Output is correct
24 Correct 1122 ms 93364 KB Output is correct
25 Correct 1169 ms 93372 KB Output is correct
26 Correct 599 ms 75600 KB Output is correct
27 Correct 605 ms 75756 KB Output is correct
28 Correct 579 ms 75640 KB Output is correct
29 Correct 580 ms 75536 KB Output is correct
30 Correct 586 ms 75844 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 34 ms 35612 KB Output is correct
3 Correct 34 ms 35704 KB Output is correct
4 Correct 34 ms 35672 KB Output is correct
5 Correct 34 ms 35576 KB Output is correct
6 Correct 33 ms 35580 KB Output is correct
7 Correct 33 ms 35576 KB Output is correct
8 Correct 34 ms 35576 KB Output is correct
9 Correct 33 ms 35576 KB Output is correct
10 Correct 35 ms 35576 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 78128 KB Output is correct
2 Correct 738 ms 93604 KB Output is correct
3 Correct 768 ms 93776 KB Output is correct
4 Correct 247 ms 71448 KB Output is correct
5 Correct 745 ms 93716 KB Output is correct
6 Correct 736 ms 93748 KB Output is correct
7 Correct 762 ms 93576 KB Output is correct
8 Correct 771 ms 93648 KB Output is correct
9 Correct 782 ms 93724 KB Output is correct
10 Correct 774 ms 93780 KB Output is correct
11 Correct 773 ms 93620 KB Output is correct
12 Correct 807 ms 93632 KB Output is correct
13 Correct 764 ms 93892 KB Output is correct
14 Correct 765 ms 93896 KB Output is correct
15 Correct 803 ms 93784 KB Output is correct
16 Correct 792 ms 93644 KB Output is correct
17 Correct 788 ms 93620 KB Output is correct
18 Correct 778 ms 93788 KB Output is correct
19 Correct 272 ms 74148 KB Output is correct
20 Correct 747 ms 93848 KB Output is correct
21 Correct 696 ms 93588 KB Output is correct
22 Correct 220 ms 75748 KB Output is correct
23 Correct 254 ms 71068 KB Output is correct
24 Correct 212 ms 75620 KB Output is correct
25 Correct 213 ms 75868 KB Output is correct
26 Correct 263 ms 70924 KB Output is correct
27 Correct 234 ms 71560 KB Output is correct
28 Correct 206 ms 76100 KB Output is correct
29 Correct 242 ms 71592 KB Output is correct
30 Correct 216 ms 75748 KB Output is correct
31 Correct 236 ms 71496 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 35576 KB Output is correct
2 Correct 38 ms 35960 KB Output is correct
3 Correct 38 ms 35960 KB Output is correct
4 Correct 34 ms 35576 KB Output is correct
5 Correct 42 ms 36064 KB Output is correct
6 Correct 38 ms 35960 KB Output is correct
7 Correct 33 ms 35704 KB Output is correct
8 Correct 34 ms 35704 KB Output is correct
9 Correct 38 ms 35960 KB Output is correct
10 Correct 38 ms 35960 KB Output is correct
11 Correct 43 ms 35960 KB Output is correct
12 Correct 38 ms 35960 KB Output is correct
13 Correct 38 ms 35992 KB Output is correct
14 Correct 39 ms 35960 KB Output is correct
15 Correct 38 ms 35960 KB Output is correct
16 Correct 596 ms 65236 KB Output is correct
17 Correct 1149 ms 93400 KB Output is correct
18 Correct 112 ms 41708 KB Output is correct
19 Correct 586 ms 75752 KB Output is correct
20 Correct 1130 ms 93388 KB Output is correct
21 Correct 787 ms 78032 KB Output is correct
22 Correct 617 ms 74648 KB Output is correct
23 Correct 1147 ms 93480 KB Output is correct
24 Correct 1122 ms 93364 KB Output is correct
25 Correct 1169 ms 93372 KB Output is correct
26 Correct 599 ms 75600 KB Output is correct
27 Correct 605 ms 75756 KB Output is correct
28 Correct 579 ms 75640 KB Output is correct
29 Correct 580 ms 75536 KB Output is correct
30 Correct 586 ms 75844 KB Output is correct
31 Correct 34 ms 35576 KB Output is correct
32 Correct 34 ms 35612 KB Output is correct
33 Correct 34 ms 35704 KB Output is correct
34 Correct 34 ms 35672 KB Output is correct
35 Correct 34 ms 35576 KB Output is correct
36 Correct 33 ms 35580 KB Output is correct
37 Correct 33 ms 35576 KB Output is correct
38 Correct 34 ms 35576 KB Output is correct
39 Correct 33 ms 35576 KB Output is correct
40 Correct 35 ms 35576 KB Output is correct
41 Correct 398 ms 78128 KB Output is correct
42 Correct 738 ms 93604 KB Output is correct
43 Correct 768 ms 93776 KB Output is correct
44 Correct 247 ms 71448 KB Output is correct
45 Correct 745 ms 93716 KB Output is correct
46 Correct 736 ms 93748 KB Output is correct
47 Correct 762 ms 93576 KB Output is correct
48 Correct 771 ms 93648 KB Output is correct
49 Correct 782 ms 93724 KB Output is correct
50 Correct 774 ms 93780 KB Output is correct
51 Correct 773 ms 93620 KB Output is correct
52 Correct 807 ms 93632 KB Output is correct
53 Correct 764 ms 93892 KB Output is correct
54 Correct 765 ms 93896 KB Output is correct
55 Correct 803 ms 93784 KB Output is correct
56 Correct 792 ms 93644 KB Output is correct
57 Correct 788 ms 93620 KB Output is correct
58 Correct 778 ms 93788 KB Output is correct
59 Correct 272 ms 74148 KB Output is correct
60 Correct 747 ms 93848 KB Output is correct
61 Correct 696 ms 93588 KB Output is correct
62 Correct 220 ms 75748 KB Output is correct
63 Correct 254 ms 71068 KB Output is correct
64 Correct 212 ms 75620 KB Output is correct
65 Correct 213 ms 75868 KB Output is correct
66 Correct 263 ms 70924 KB Output is correct
67 Correct 234 ms 71560 KB Output is correct
68 Correct 206 ms 76100 KB Output is correct
69 Correct 242 ms 71592 KB Output is correct
70 Correct 216 ms 75748 KB Output is correct
71 Correct 236 ms 71496 KB Output is correct
72 Correct 822 ms 78760 KB Output is correct
73 Correct 1186 ms 94412 KB Output is correct
74 Correct 1190 ms 94272 KB Output is correct
75 Correct 1171 ms 95336 KB Output is correct
76 Correct 1167 ms 95696 KB Output is correct
77 Correct 1163 ms 95984 KB Output is correct
78 Correct 1171 ms 95980 KB Output is correct
79 Correct 1125 ms 95684 KB Output is correct
80 Correct 1159 ms 95620 KB Output is correct
81 Correct 1170 ms 95824 KB Output is correct
82 Correct 1176 ms 95708 KB Output is correct
83 Correct 1169 ms 95540 KB Output is correct
84 Correct 1144 ms 95868 KB Output is correct
85 Correct 1146 ms 96316 KB Output is correct
86 Correct 1149 ms 95944 KB Output is correct
87 Correct 1175 ms 96000 KB Output is correct
88 Correct 1217 ms 95636 KB Output is correct
89 Correct 644 ms 75936 KB Output is correct
90 Correct 1175 ms 95612 KB Output is correct
91 Correct 1087 ms 95560 KB Output is correct
92 Correct 625 ms 76796 KB Output is correct
93 Correct 606 ms 72540 KB Output is correct
94 Correct 613 ms 76636 KB Output is correct
95 Correct 619 ms 76940 KB Output is correct
96 Correct 614 ms 71972 KB Output is correct
97 Correct 628 ms 72984 KB Output is correct
98 Correct 619 ms 77256 KB Output is correct
99 Correct 646 ms 73272 KB Output is correct
100 Correct 611 ms 76764 KB Output is correct