oj.uz

Submission #429914

# Submission time Handle Problem Language Result Execution time Memory
429914 2021-06-16T10:27:00 Z marcipan5000 Swapping Cities (APIO20_swap) C++14
100 / 100
 1327 ms 65612 KB 
#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

//bin_climb_str
struct climb{
    int w,x,y;
};

//seg_tree
struct pont{
    int a,b;
    int bal,jobb;
    int e;
};

vector<int> f;
pont t[500001];
int p1=0;
int fa;

int seg_build(int x,int y) {
    int p2=p1; p1++;
    t[p2].a=x; t[p2].b=y;
    if (x==y) {
        t[p2].e=f[x];
        return(p2);
    }
    t[p2].bal=seg_build(x,(x+y)/2);
    t[p2].jobb=seg_build((x+y)/2+1,y);
    t[p2].e=min(t[t[p2].bal].e,t[t[p2].jobb].e);
    return(p2);
}

int seg_find(int q,int x,int y) {
    if ((t[q].a>y)||(t[q].b<x)) {
        return(1e8);
    }
    if ((t[q].a>=x)&&(t[q].b<=y)) {
        return(t[q].e);
    }
    return(min(seg_find(t[q].bal,x,y),seg_find(t[q].jobb,x,y)));
}

struct el{
    int w,x;
};

struct elek{
    int a,b,w;
};

bool comp(elek a,elek b) {
    return((a.w<b.w)||((a.w==b.w)&&(a.a<b.a)));
}

bool comp2(el a,el b) {
    return((a.w<b.w)||((a.w==b.w)&&(a.x<b.x)));
}

vector<el> t1[100001];
int n,m;
el z;
int har[100001];

vector<el> t2[100001];
vector<elek> g;
elek z2;

//dsu
int r[100001];
int s[100001];
void dsu_init() {
    for (int i=0;i<n;i++) {
        r[i]=i;
        s[i]=1;
    }
}

int dsu_find(int a) {
    if (a==r[a]) {
        return(a);
    }
    r[a]=dsu_find(r[a]);
    return(r[a]);
}

void dsu_merge(int a,int b) {
    if (s[a]<s[b]) {
        r[a]=b;
    } else {
        r[b]=a;
    }
}

//bin_climb
vector<climb> cl[100001];
climb z3;

//dfs
int h[100001];
int l=1;
int d[100001];
int c[100001];
int par[100001];
int par2[100001];
void dfs(int p) {
    h[p]=l;
    d[l]=p; l++;
    c[p]=f.size();
    f.push_back(h[p]);

    if (p>0) {
        z3.w=par2[p];
        z3.x=par[p];
        z3.y=har[par[p]];
        cl[p].push_back(z3);
        int e=0;
        while (e>-1) {
            if (cl[cl[p][e].x].size()>e) {
                z3.x=cl[cl[p][e].x][e].x;
                z3.w=max(cl[p][e].w,cl[cl[p][e].x][e].w);
                z3.y=min(cl[p][e].y,cl[cl[p][e].x][e].y);
                cl[p].push_back(z3);
                e++;
            } else {
                e=-1;
            }
        }
    }

    for (int i=0;i<t2[p].size();i++) {
        if (h[t2[p][i].x]==0) {
            par[t2[p][i].x]=p;
            par2[t2[p][i].x]=t2[p][i].w;
            dfs(t2[p][i].x);

            f.push_back(h[p]);
        }
    }
}

int lca(int a,int b) {
    return(d[seg_find(fa,min(c[a],c[b]),max(c[a],c[b]))]);
}

//update
void dff(int p,int ha) {
    har[p]=ha;
    for (int i=0;i<t1[p].size();i++) {
        if (har[t1[p][i].x]>max(ha,t1[p][i].w)) {
            dff(t1[p][i].x,max(ha,t1[p][i].w));
        }
    }
}

vector<el> o;
void init(int N1, int M1, std::vector<int> U1, std::vector<int> V1, std::vector<int> W1) {
    n=N1;
    m=M1;
    for (int i=0;i<m;i++) {
        z.w=W1[i];
        z.x=V1[i];
        t1[U1[i]].push_back(z);
        z.x=U1[i];
        t1[V1[i]].push_back(z);


        z2.a=U1[i];
        z2.b=V1[i];
        z2.w=W1[i];
        g.push_back(z2);
    }
    for (int i=0;i<n;i++) {
        sort(t1[i].begin(),t1[i].end(),comp2);
        if (t1[i].size()>=3) {
            har[i]=t1[i][2].w;
        } else {
            har[i]=1e9;
        }
    }
    dsu_init();
    sort(g.begin(),g.end(),comp);
    for (int i=0;i<m;i++) {
        if (dsu_find(g[i].a)!=dsu_find(g[i].b)) {
            dsu_merge(dsu_find(g[i].a),dsu_find(g[i].b));
            z.w=g[i].w;
            z.x=g[i].a;
            t2[g[i].b].push_back(z);
            z.x=g[i].b;
            t2[g[i].a].push_back(z);
        } else {
            har[g[i].a]=min(har[g[i].a],g[i].w);
            har[g[i].b]=min(har[g[i].b],g[i].w);
        }
    }
    for (int i=0;i<n;i++) {
        z.w=har[i];
        z.x=i;
        o.push_back(z);
    }
    sort(o.begin(),o.end(),comp2);
    for (int i=0;i<n;i++) {
        dff(i,har[i]);
    }
    par[0]=-1;
    dfs(0);
    fa=seg_build(0,f.size()-1);
}

pair<int,int> get_climb(int fr,int ma,int q) {
    pair<int,int> ans;
    pair<int,int> ker;
    ans.first=0;
    ans.second=1e9;
    if (fr==ma) {
        return(ans);
    }
    int l=min(q,int(cl[fr].size())-1);
    while ((l>=0)&&(h[cl[fr][l].x]<h[ma])) {
        l--;
    }
    ker=get_climb(cl[fr][l].x,ma,l-1);
    ans.first=max(ker.first,cl[fr][l].w);
    ans.second=min(ker.second,cl[fr][l].y);
    return(ans);
}

int getMinimumFuelCapacity(int X1, int Y1) {
    int r1,r2,r3;
    int x,y;
    x=X1; y=Y1;
    int lca2=lca(x,y);
    pair<int,int> ker;
    ker=get_climb(x,lca2,100);
    r1=0;
    r2=min(har[x],har[y]);
    r1=max(r1,ker.first);
    r2=min(r2,ker.second);
    ker=get_climb(y,lca2,100);
    r1=max(r1,ker.first);
    r2=min(r2,ker.second);
    r3=max(r1,r2);
    if (r3==1e9) {
        return(-1);
    } else {
        return(r3);
    }
}

Compilation message

swap.cpp: In function 'void dfs(int)':
swap.cpp:121:38: warning: comparison of integer expressions of different signedness: 'std::vector<climb>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  121 |             if (cl[cl[p][e].x].size()>e) {
      |                 ~~~~~~~~~~~~~~~~~~~~~^~
swap.cpp:133:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<el>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (int i=0;i<t2[p].size();i++) {
      |                  ~^~~~~~~~~~~~~
swap.cpp: In function 'void dff(int, int)':
swap.cpp:151:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<el>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |     for (int i=0;i<t1[p].size();i++) {
      |                  ~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 6 ms 7304 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 6 ms 7428 KB Output is correct
5 Correct 9 ms 7752 KB Output is correct
6 Correct 7 ms 7660 KB Output is correct
7 Correct 7 ms 7756 KB Output is correct
8 Correct 9 ms 7756 KB Output is correct
9 Correct 258 ms 45052 KB Output is correct
10 Correct 278 ms 56040 KB Output is correct
11 Correct 263 ms 53876 KB Output is correct
12 Correct 306 ms 58228 KB Output is correct
13 Correct 298 ms 64256 KB Output is correct
14 Correct 275 ms 44476 KB Output is correct
15 Correct 1069 ms 57724 KB Output is correct
16 Correct 965 ms 53120 KB Output is correct
17 Correct 1179 ms 65612 KB Output is correct
18 Correct 1169 ms 61340 KB Output is correct
19 Correct 305 ms 18700 KB Output is correct
20 Correct 941 ms 56652 KB Output is correct
21 Correct 1024 ms 54680 KB Output is correct
22 Correct 1066 ms 59096 KB Output is correct
23 Correct 1225 ms 61280 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 6 ms 7304 KB Output is correct
3 Correct 570 ms 35884 KB Output is correct
4 Correct 511 ms 37236 KB Output is correct
5 Correct 532 ms 36456 KB Output is correct
6 Correct 498 ms 37012 KB Output is correct
7 Correct 546 ms 36876 KB Output is correct
8 Correct 556 ms 35768 KB Output is correct
9 Correct 556 ms 36584 KB Output is correct
10 Correct 527 ms 35520 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 6 ms 7304 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 6 ms 7428 KB Output is correct
5 Correct 9 ms 7752 KB Output is correct
6 Correct 7 ms 7660 KB Output is correct
7 Correct 7 ms 7756 KB Output is correct
8 Correct 9 ms 7756 KB Output is correct
9 Correct 5 ms 7372 KB Output is correct
10 Correct 8 ms 7628 KB Output is correct
11 Correct 6 ms 7756 KB Output is correct
12 Correct 7 ms 7628 KB Output is correct
13 Correct 6 ms 7628 KB Output is correct
14 Correct 7 ms 7628 KB Output is correct
15 Correct 7 ms 7628 KB Output is correct
16 Correct 7 ms 7756 KB Output is correct
17 Correct 7 ms 7756 KB Output is correct
18 Correct 6 ms 7628 KB Output is correct
19 Correct 8 ms 7628 KB Output is correct
20 Correct 8 ms 7756 KB Output is correct
21 Correct 6 ms 7628 KB Output is correct
22 Correct 6 ms 7492 KB Output is correct
23 Correct 8 ms 7628 KB Output is correct
24 Correct 9 ms 7756 KB Output is correct
25 Correct 7 ms 7756 KB Output is correct
26 Correct 7 ms 7708 KB Output is correct
27 Correct 6 ms 7756 KB Output is correct
28 Correct 7 ms 7756 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 7 ms 7372 KB Output is correct
3 Correct 6 ms 7304 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 6 ms 7428 KB Output is correct
6 Correct 9 ms 7752 KB Output is correct
7 Correct 7 ms 7660 KB Output is correct
8 Correct 7 ms 7756 KB Output is correct
9 Correct 9 ms 7756 KB Output is correct
10 Correct 258 ms 45052 KB Output is correct
11 Correct 278 ms 56040 KB Output is correct
12 Correct 263 ms 53876 KB Output is correct
13 Correct 306 ms 58228 KB Output is correct
14 Correct 298 ms 64256 KB Output is correct
15 Correct 8 ms 7628 KB Output is correct
16 Correct 6 ms 7756 KB Output is correct
17 Correct 7 ms 7628 KB Output is correct
18 Correct 6 ms 7628 KB Output is correct
19 Correct 7 ms 7628 KB Output is correct
20 Correct 7 ms 7628 KB Output is correct
21 Correct 7 ms 7756 KB Output is correct
22 Correct 7 ms 7756 KB Output is correct
23 Correct 6 ms 7628 KB Output is correct
24 Correct 8 ms 7628 KB Output is correct
25 Correct 8 ms 7756 KB Output is correct
26 Correct 6 ms 7628 KB Output is correct
27 Correct 6 ms 7492 KB Output is correct
28 Correct 8 ms 7628 KB Output is correct
29 Correct 9 ms 7756 KB Output is correct
30 Correct 7 ms 7756 KB Output is correct
31 Correct 7 ms 7708 KB Output is correct
32 Correct 6 ms 7756 KB Output is correct
33 Correct 7 ms 7756 KB Output is correct
34 Correct 28 ms 12004 KB Output is correct
35 Correct 356 ms 56012 KB Output is correct
36 Correct 339 ms 52744 KB Output is correct
37 Correct 335 ms 50832 KB Output is correct
38 Correct 322 ms 49788 KB Output is correct
39 Correct 309 ms 48640 KB Output is correct
40 Correct 273 ms 44960 KB Output is correct
41 Correct 444 ms 53420 KB Output is correct
42 Correct 358 ms 54972 KB Output is correct
43 Correct 345 ms 58864 KB Output is correct
44 Correct 350 ms 50352 KB Output is correct
45 Correct 286 ms 38460 KB Output is correct
46 Correct 327 ms 52004 KB Output is correct
47 Correct 320 ms 49612 KB Output is correct
48 Correct 330 ms 41140 KB Output is correct
49 Correct 123 ms 18416 KB Output is correct
50 Correct 93 ms 16816 KB Output is correct
51 Correct 225 ms 33096 KB Output is correct
52 Correct 507 ms 55768 KB Output is correct
53 Correct 410 ms 46876 KB Output is correct
54 Correct 516 ms 60112 KB Output is correct
55 Correct 337 ms 63436 KB Output is correct
56 Correct 411 ms 47752 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7372 KB Output is correct
2 Correct 6 ms 7304 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 6 ms 7428 KB Output is correct
5 Correct 9 ms 7752 KB Output is correct
6 Correct 7 ms 7660 KB Output is correct
7 Correct 7 ms 7756 KB Output is correct
8 Correct 9 ms 7756 KB Output is correct
9 Correct 258 ms 45052 KB Output is correct
10 Correct 278 ms 56040 KB Output is correct
11 Correct 263 ms 53876 KB Output is correct
12 Correct 306 ms 58228 KB Output is correct
13 Correct 298 ms 64256 KB Output is correct
14 Correct 275 ms 44476 KB Output is correct
15 Correct 1069 ms 57724 KB Output is correct
16 Correct 965 ms 53120 KB Output is correct
17 Correct 1179 ms 65612 KB Output is correct
18 Correct 1169 ms 61340 KB Output is correct
19 Correct 570 ms 35884 KB Output is correct
20 Correct 511 ms 37236 KB Output is correct
21 Correct 532 ms 36456 KB Output is correct
22 Correct 498 ms 37012 KB Output is correct
23 Correct 546 ms 36876 KB Output is correct
24 Correct 556 ms 35768 KB Output is correct
25 Correct 556 ms 36584 KB Output is correct
26 Correct 527 ms 35520 KB Output is correct
27 Correct 8 ms 7628 KB Output is correct
28 Correct 6 ms 7756 KB Output is correct
29 Correct 7 ms 7628 KB Output is correct
30 Correct 6 ms 7628 KB Output is correct
31 Correct 7 ms 7628 KB Output is correct
32 Correct 7 ms 7628 KB Output is correct
33 Correct 7 ms 7756 KB Output is correct
34 Correct 7 ms 7756 KB Output is correct
35 Correct 6 ms 7628 KB Output is correct
36 Correct 28 ms 12004 KB Output is correct
37 Correct 356 ms 56012 KB Output is correct
38 Correct 339 ms 52744 KB Output is correct
39 Correct 335 ms 50832 KB Output is correct
40 Correct 322 ms 49788 KB Output is correct
41 Correct 309 ms 48640 KB Output is correct
42 Correct 273 ms 44960 KB Output is correct
43 Correct 444 ms 53420 KB Output is correct
44 Correct 358 ms 54972 KB Output is correct
45 Correct 345 ms 58864 KB Output is correct
46 Correct 350 ms 50352 KB Output is correct
47 Correct 56 ms 12624 KB Output is correct
48 Correct 1106 ms 56416 KB Output is correct
49 Correct 1218 ms 54776 KB Output is correct
50 Correct 1070 ms 53772 KB Output is correct
51 Correct 1169 ms 53116 KB Output is correct
52 Correct 1032 ms 49800 KB Output is correct
53 Correct 693 ms 36784 KB Output is correct
54 Correct 1120 ms 56288 KB Output is correct
55 Correct 1158 ms 56824 KB Output is correct
56 Correct 1277 ms 63552 KB Output is correct
57 Correct 948 ms 53524 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 7 ms 7372 KB Output is correct
3 Correct 6 ms 7304 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 6 ms 7428 KB Output is correct
6 Correct 9 ms 7752 KB Output is correct
7 Correct 7 ms 7660 KB Output is correct
8 Correct 7 ms 7756 KB Output is correct
9 Correct 9 ms 7756 KB Output is correct
10 Correct 258 ms 45052 KB Output is correct
11 Correct 278 ms 56040 KB Output is correct
12 Correct 263 ms 53876 KB Output is correct
13 Correct 306 ms 58228 KB Output is correct
14 Correct 298 ms 64256 KB Output is correct
15 Correct 275 ms 44476 KB Output is correct
16 Correct 1069 ms 57724 KB Output is correct
17 Correct 965 ms 53120 KB Output is correct
18 Correct 1179 ms 65612 KB Output is correct
19 Correct 1169 ms 61340 KB Output is correct
20 Correct 570 ms 35884 KB Output is correct
21 Correct 511 ms 37236 KB Output is correct
22 Correct 532 ms 36456 KB Output is correct
23 Correct 498 ms 37012 KB Output is correct
24 Correct 546 ms 36876 KB Output is correct
25 Correct 556 ms 35768 KB Output is correct
26 Correct 556 ms 36584 KB Output is correct
27 Correct 527 ms 35520 KB Output is correct
28 Correct 8 ms 7628 KB Output is correct
29 Correct 6 ms 7756 KB Output is correct
30 Correct 7 ms 7628 KB Output is correct
31 Correct 6 ms 7628 KB Output is correct
32 Correct 7 ms 7628 KB Output is correct
33 Correct 7 ms 7628 KB Output is correct
34 Correct 7 ms 7756 KB Output is correct
35 Correct 7 ms 7756 KB Output is correct
36 Correct 6 ms 7628 KB Output is correct
37 Correct 28 ms 12004 KB Output is correct
38 Correct 356 ms 56012 KB Output is correct
39 Correct 339 ms 52744 KB Output is correct
40 Correct 335 ms 50832 KB Output is correct
41 Correct 322 ms 49788 KB Output is correct
42 Correct 309 ms 48640 KB Output is correct
43 Correct 273 ms 44960 KB Output is correct
44 Correct 444 ms 53420 KB Output is correct
45 Correct 358 ms 54972 KB Output is correct
46 Correct 345 ms 58864 KB Output is correct
47 Correct 350 ms 50352 KB Output is correct
48 Correct 56 ms 12624 KB Output is correct
49 Correct 1106 ms 56416 KB Output is correct
50 Correct 1218 ms 54776 KB Output is correct
51 Correct 1070 ms 53772 KB Output is correct
52 Correct 1169 ms 53116 KB Output is correct
53 Correct 1032 ms 49800 KB Output is correct
54 Correct 693 ms 36784 KB Output is correct
55 Correct 1120 ms 56288 KB Output is correct
56 Correct 1158 ms 56824 KB Output is correct
57 Correct 1277 ms 63552 KB Output is correct
58 Correct 948 ms 53524 KB Output is correct
59 Correct 305 ms 18700 KB Output is correct
60 Correct 941 ms 56652 KB Output is correct
61 Correct 1024 ms 54680 KB Output is correct
62 Correct 1066 ms 59096 KB Output is correct
63 Correct 1225 ms 61280 KB Output is correct
64 Correct 8 ms 7628 KB Output is correct
65 Correct 8 ms 7756 KB Output is correct
66 Correct 6 ms 7628 KB Output is correct
67 Correct 6 ms 7492 KB Output is correct
68 Correct 8 ms 7628 KB Output is correct
69 Correct 9 ms 7756 KB Output is correct
70 Correct 7 ms 7756 KB Output is correct
71 Correct 7 ms 7708 KB Output is correct
72 Correct 6 ms 7756 KB Output is correct
73 Correct 7 ms 7756 KB Output is correct
74 Correct 286 ms 38460 KB Output is correct
75 Correct 327 ms 52004 KB Output is correct
76 Correct 320 ms 49612 KB Output is correct
77 Correct 330 ms 41140 KB Output is correct
78 Correct 123 ms 18416 KB Output is correct
79 Correct 93 ms 16816 KB Output is correct
80 Correct 225 ms 33096 KB Output is correct
81 Correct 507 ms 55768 KB Output is correct
82 Correct 410 ms 46876 KB Output is correct
83 Correct 516 ms 60112 KB Output is correct
84 Correct 337 ms 63436 KB Output is correct
85 Correct 411 ms 47752 KB Output is correct
86 Correct 171 ms 19860 KB Output is correct
87 Correct 1113 ms 54428 KB Output is correct
88 Correct 1118 ms 54616 KB Output is correct
89 Correct 886 ms 41468 KB Output is correct
90 Correct 294 ms 20088 KB Output is correct
91 Correct 427 ms 21752 KB Output is correct
92 Correct 762 ms 35728 KB Output is correct
93 Correct 1327 ms 58616 KB Output is correct
94 Correct 1129 ms 49772 KB Output is correct
95 Correct 1213 ms 61372 KB Output is correct
96 Correct 1174 ms 57436 KB Output is correct
97 Correct 923 ms 47500 KB Output is correct