oj.uz

Submission #283000

# Submission time Handle Problem Language Result Execution time Memory
283000 2020-08-25T08:29:25 Z 문홍윤(#5763) Iqea (innopolis2018_final_C) C++17
36 / 100
 2000 ms 109300 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef pair<int, int> pii;
const int inf=1e9;

int n, rex, rey;
unordered_map<int, int> mx[100010], my[100010];
pii p[100010];
vector<int> lx[100010], ly[100010];

bool cmp(pii a, pii b){return mp(a.S, a.F)<mp(b.S, b.F);}
inline void make_tree(){
    sort(p+1, p+n+1);
    for(int i=1; i<=n; i++){
        if(p[i].F!=p[i-1].F||p[i].S!=p[i-1].S+1)rex++;
        mx[p[i].F][p[i].S]=rex;
    }
    sort(p+1, p+n+1, cmp);
    for(int i=1; i<=n; i++){
        if(p[i].S!=p[i-1].S||p[i].F!=p[i-1].F+1)rey++;
        my[p[i].F][p[i].S]=rey;
    }
    for(int i=1; i<=n; i++){
        if(mx[p[i].F+1][p[i].S]){
            lx[mx[p[i].F][p[i].S]].eb(mx[p[i].F+1][p[i].S]);
            lx[mx[p[i].F+1][p[i].S]].eb(mx[p[i].F][p[i].S]);
        }
        if(my[p[i].F][p[i].S+1]){
            ly[my[p[i].F][p[i].S]].eb(my[p[i].F][p[i].S+1]);
            ly[my[p[i].F][p[i].S+1]].eb(my[p[i].F][p[i].S]);
        }
    }
    for(int i=1; i<=rex; i++){
        svec(lx[i]);
        press(lx[i]);
    }
    for(int i=1; i<=rey; i++){
        svec(ly[i]);
        press(ly[i]);
    }
}

int sz[100010];
bool ch[100010];
void dfs_x(int num, int par){
    sz[num]=1;
    for(auto i:lx[num]){
        if(i==par||ch[i])continue;
        dfs_x(i, num);
        sz[num]+=sz[i];
    }
}
int get_cen_x(int num, int siz){
    int ov=0;
    for(auto i:lx[num]){
        if(ch[i])continue;
        if(sz[i]>siz/2){
            ov=i;
            break;
        }
    }
    if(!ov)return num;
    sz[num]=siz-sz[ov];
    sz[ov]=siz;
    return get_cen_x(ov, siz);
}
void dfs_y(int num, int par){
    sz[num]=1;
    for(auto i:ly[num]){
        if(i==par||ch[i])continue;
        dfs_y(i, num);
        sz[num]+=sz[i];
    }
}
int get_cen_y(int num, int siz){
    int ov=0;
    for(auto i:ly[num]){
        if(ch[i])continue;
        if(sz[i]>siz/2){
            ov=i;
            break;
        }
    }
    if(!ov)return num;
    sz[num]=siz-sz[ov];
    sz[ov]=siz;
    return get_cen_y(ov, siz);
}

int cpar_x[100010], cpar_y[100010];
int d_x[100010][20], d_y[100010][20];

void make_cen_x(int num, int par){
    dfs_x(num, par);
    int cen=get_cen_x(num, sz[num]);
    cpar_x[cen]=par;
    ch[cen]=true;
    for(auto i:lx[cen]){
        if(ch[i])continue;
        make_cen_x(i, cen);
    }
}
void make_cen_y(int num, int par){
    dfs_y(num, par);
    int cen=get_cen_y(num, sz[num]);
    cpar_y[cen]=par;
    ch[cen]=true;
    for(auto i:ly[cen]){
        if(ch[i])continue;
        make_cen_y(i, cen);
    }
}

int dep_x[100010], dep_y[100010];
int sp_x[100010][20], sp_y[100010][20];
void dfs2_x(int num, int par){
    dep_x[num]=dep_x[par]+1;
    sp_x[num][0]=par;
    for(auto i:lx[num]){
        if(i==par)continue;
        dfs2_x(i, num);
    }
}
void dfs2_y(int num, int par){
    dep_y[num]=dep_y[par]+1;
    sp_y[num][0]=par;
    for(auto i:ly[num]){
        if(i==par)continue;
        dfs2_y(i, num);
    }
}

inline int lca_x(int x, int y){
    if(dep_x[x]>dep_x[y])swap(x, y);
    for(int i=19; i>=0; i--){
        if(dep_x[y]-dep_x[x]>=(1<<i))y=sp_x[y][i];
    }
    if(x==y)return x;
    for(int i=19; i>=0; i--){
        if(sp_x[x][i]!=sp_x[y][i]){
            x=sp_x[x][i];
            y=sp_x[y][i];
        }
    }
    return sp_x[x][0];
}
inline int lca_y(int x, int y){
    if(dep_y[x]>dep_y[y])swap(x, y);
    for(int i=19; i>=0; i--){
        if(dep_y[y]-dep_y[x]>=(1<<i))y=sp_y[y][i];
    }
    if(x==y)return x;
    for(int i=19; i>=0; i--){
        if(sp_y[x][i]!=sp_y[y][i]){
            x=sp_y[x][i];
            y=sp_y[y][i];
        }
    }
    return sp_y[x][0];
}
inline int getd_x(int x, int y){return dep_x[x]+dep_x[y]-2*dep_x[lca_x(x, y)];}
inline int getd_y(int x, int y){return dep_y[x]+dep_y[y]-2*dep_y[lca_y(x, y)];}

inline void get_cend_x(){
    for(int i=1; i<=rex; i++){
        int nw=cpar_x[i];
        for(int j=1; nw; j++, nw=cpar_x[nw])d_x[i][j]=getd_x(i, nw);
    }
}
inline void get_cend_y(){
    for(int i=1; i<=rey; i++){
        int nw=cpar_y[i];
        for(int j=1; nw; j++, nw=cpar_y[nw])d_y[i][j]=getd_y(i, nw);
    }
}

map<int, int> arr[100010];

inline void upd(int x, int y){
    int nx=mx[x][y], ny=my[x][y];
    int tx=nx, ty=ny;
    for(int i=0; tx; i++, tx=cpar_x[tx]){
        ty=ny;
        for(int j=0; ty; j++, ty=cpar_y[ty]){
            int tmp=d_x[nx][i]+d_y[ny][j]+1;
            if(!arr[tx][ty])arr[tx][ty]=inf;
            arr[tx][ty]=min(tmp, arr[tx][ty]);
        }
    }
}
inline int query(int x, int y){
    int nx=mx[x][y], ny=my[x][y], ret=inf;
    int tx=nx, ty=ny;
    for(int i=0; tx; i++, tx=cpar_x[tx]){
        ty=ny;
        for(int j=0; ty; j++, ty=cpar_y[ty]){
            if(!arr[tx][ty])continue;
            int tmp=d_x[nx][i]+d_y[ny][j];
            ret=min(ret, arr[tx][ty]+tmp-1);
        }
    }
    return ret==inf?-1:ret;
}

inline int readChar();
template<class T=int> inline T readInt();
static const int buf_size=4096;
inline int getChar(){
    static char buf[buf_size];
    static int len=0, pos=0;
    if(pos==len)pos=0, len=fread(buf, 1, buf_size, stdin);
    if(pos==len)return -1;
    return buf[pos++];
}
inline int readChar(){
    int c=getChar();
    while(c<=32)c=getChar();
    return c;
}
template <class T>
inline T readInt(){
    int s=1, c=readChar();
    T x=0;
    if(c=='-')s=-1, c=getChar();
    while('0'<= c&&c<='9')x=x*10+c-'0', c=getChar();
    return s==1?x:-x;
}

int main(){
    //scanf("%d", &n);
    n=readInt();
    for(int i=1; i<=n; i++){
        //scanf("%d %d", &p[i].F, &p[i].S);
        p[i].F=readInt(); p[i].S=readInt();
    }
    make_tree();
    make_cen_x(1, 0);
    memset(ch, 0, sizeof ch);
    make_cen_y(1, 0);
    dfs2_x(1, 0);
    dfs2_y(1, 0);
    for(int j=1; j<20; j++){
        for(int i=1; i<=rex; i++)sp_x[i][j]=sp_x[sp_x[i][j-1]][j-1];
        for(int i=1; i<=rey; i++)sp_y[i][j]=sp_y[sp_y[i][j-1]][j-1];
    }
    get_cend_x();
    get_cend_y();
    int q;
    //scanf("%d", &q);
    q=readInt();
    for(int i=1; i<=q; i++){
        int a, b, c;
        //scanf("%d %d %d", &a, &b, &c);
        a=readInt(); b=readInt(); c=readInt();
        if(a==1)upd(b, c);
        else printf("%d\n", query(b, c));
    }
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20864 KB Output is correct
2 Correct 16 ms 20864 KB Output is correct
3 Correct 15 ms 20864 KB Output is correct
4 Correct 33 ms 21868 KB Output is correct
5 Correct 35 ms 21888 KB Output is correct
6 Correct 33 ms 22008 KB Output is correct
7 Correct 49 ms 23800 KB Output is correct
8 Correct 56 ms 23928 KB Output is correct
9 Correct 55 ms 24056 KB Output is correct
10 Correct 58 ms 23800 KB Output is correct
11 Correct 58 ms 23928 KB Output is correct
12 Correct 56 ms 23928 KB Output is correct
13 Correct 56 ms 24056 KB Output is correct
14 Correct 56 ms 23928 KB Output is correct
15 Correct 57 ms 24056 KB Output is correct
16 Correct 51 ms 23800 KB Output is correct
17 Correct 50 ms 23692 KB Output is correct
18 Correct 58 ms 23800 KB Output is correct
19 Correct 62 ms 23544 KB Output is correct
20 Correct 59 ms 24056 KB Output is correct
21 Correct 55 ms 23928 KB Output is correct
22 Correct 61 ms 24440 KB Output is correct
23 Correct 62 ms 24440 KB Output is correct
24 Correct 67 ms 24824 KB Output is correct
25 Correct 30 ms 23544 KB Output is correct
26 Correct 33 ms 23800 KB Output is correct
27 Correct 30 ms 23168 KB Output is correct
28 Correct 65 ms 24820 KB Output is correct
29 Correct 66 ms 24824 KB Output is correct
30 Correct 67 ms 25016 KB Output is correct
31 Correct 69 ms 24952 KB Output is correct
32 Correct 84 ms 24824 KB Output is correct
33 Correct 79 ms 24824 KB Output is correct
34 Correct 70 ms 24824 KB Output is correct
35 Correct 79 ms 24952 KB Output is correct
36 Correct 27 ms 23316 KB Output is correct
37 Correct 73 ms 24796 KB Output is correct
38 Correct 73 ms 24696 KB Output is correct
39 Correct 75 ms 24824 KB Output is correct
40 Correct 76 ms 24952 KB Output is correct
41 Correct 63 ms 24568 KB Output is correct
42 Correct 61 ms 24436 KB Output is correct
43 Correct 29 ms 23296 KB Output is correct
44 Correct 72 ms 24440 KB Output is correct
45 Correct 66 ms 24568 KB Output is correct
46 Correct 32 ms 23380 KB Output is correct
47 Correct 54 ms 23288 KB Output is correct
48 Correct 43 ms 22776 KB Output is correct
49 Correct 43 ms 22520 KB Output is correct
50 Correct 41 ms 22392 KB Output is correct
51 Correct 37 ms 22248 KB Output is correct
52 Correct 50 ms 23288 KB Output is correct
53 Correct 48 ms 23416 KB Output is correct
54 Correct 52 ms 23288 KB Output is correct
55 Correct 53 ms 23416 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20864 KB Output is correct
2 Correct 16 ms 20864 KB Output is correct
3 Correct 15 ms 20864 KB Output is correct
4 Correct 33 ms 21868 KB Output is correct
5 Correct 35 ms 21888 KB Output is correct
6 Correct 33 ms 22008 KB Output is correct
7 Correct 49 ms 23800 KB Output is correct
8 Correct 56 ms 23928 KB Output is correct
9 Correct 55 ms 24056 KB Output is correct
10 Correct 58 ms 23800 KB Output is correct
11 Correct 58 ms 23928 KB Output is correct
12 Correct 56 ms 23928 KB Output is correct
13 Correct 56 ms 24056 KB Output is correct
14 Correct 56 ms 23928 KB Output is correct
15 Correct 57 ms 24056 KB Output is correct
16 Correct 51 ms 23800 KB Output is correct
17 Correct 50 ms 23692 KB Output is correct
18 Correct 58 ms 23800 KB Output is correct
19 Correct 62 ms 23544 KB Output is correct
20 Correct 59 ms 24056 KB Output is correct
21 Correct 55 ms 23928 KB Output is correct
22 Correct 61 ms 24440 KB Output is correct
23 Correct 62 ms 24440 KB Output is correct
24 Correct 67 ms 24824 KB Output is correct
25 Correct 30 ms 23544 KB Output is correct
26 Correct 33 ms 23800 KB Output is correct
27 Correct 30 ms 23168 KB Output is correct
28 Correct 65 ms 24820 KB Output is correct
29 Correct 66 ms 24824 KB Output is correct
30 Correct 67 ms 25016 KB Output is correct
31 Correct 69 ms 24952 KB Output is correct
32 Correct 84 ms 24824 KB Output is correct
33 Correct 79 ms 24824 KB Output is correct
34 Correct 70 ms 24824 KB Output is correct
35 Correct 79 ms 24952 KB Output is correct
36 Correct 27 ms 23316 KB Output is correct
37 Correct 73 ms 24796 KB Output is correct
38 Correct 73 ms 24696 KB Output is correct
39 Correct 75 ms 24824 KB Output is correct
40 Correct 76 ms 24952 KB Output is correct
41 Correct 63 ms 24568 KB Output is correct
42 Correct 61 ms 24436 KB Output is correct
43 Correct 29 ms 23296 KB Output is correct
44 Correct 72 ms 24440 KB Output is correct
45 Correct 66 ms 24568 KB Output is correct
46 Correct 32 ms 23380 KB Output is correct
47 Correct 54 ms 23288 KB Output is correct
48 Correct 43 ms 22776 KB Output is correct
49 Correct 43 ms 22520 KB Output is correct
50 Correct 41 ms 22392 KB Output is correct
51 Correct 37 ms 22248 KB Output is correct
52 Correct 50 ms 23288 KB Output is correct
53 Correct 48 ms 23416 KB Output is correct
54 Correct 52 ms 23288 KB Output is correct
55 Correct 53 ms 23416 KB Output is correct
56 Correct 256 ms 22392 KB Output is correct
57 Correct 267 ms 22268 KB Output is correct
58 Correct 259 ms 22392 KB Output is correct
59 Correct 475 ms 24700 KB Output is correct
60 Correct 550 ms 24824 KB Output is correct
61 Correct 565 ms 25208 KB Output is correct
62 Correct 600 ms 24920 KB Output is correct
63 Correct 572 ms 24896 KB Output is correct
64 Correct 647 ms 25088 KB Output is correct
65 Correct 520 ms 24824 KB Output is correct
66 Correct 621 ms 24824 KB Output is correct
67 Correct 518 ms 24696 KB Output is correct
68 Correct 484 ms 24824 KB Output is correct
69 Correct 454 ms 24312 KB Output is correct
70 Correct 575 ms 24952 KB Output is correct
71 Correct 528 ms 24504 KB Output is correct
72 Correct 563 ms 24976 KB Output is correct
73 Correct 551 ms 24572 KB Output is correct
74 Correct 151 ms 24312 KB Output is correct
75 Correct 174 ms 24540 KB Output is correct
76 Correct 147 ms 23836 KB Output is correct
77 Correct 737 ms 25856 KB Output is correct
78 Correct 731 ms 25852 KB Output is correct
79 Correct 65 ms 24184 KB Output is correct
80 Correct 966 ms 25732 KB Output is correct
81 Correct 909 ms 25876 KB Output is correct
82 Correct 644 ms 25216 KB Output is correct
83 Correct 651 ms 25464 KB Output is correct
84 Correct 123 ms 24104 KB Output is correct
85 Correct 787 ms 25208 KB Output is correct
86 Correct 788 ms 25168 KB Output is correct
87 Correct 146 ms 23928 KB Output is correct
88 Correct 473 ms 23928 KB Output is correct
89 Correct 438 ms 23548 KB Output is correct
90 Correct 408 ms 23432 KB Output is correct
91 Correct 363 ms 22996 KB Output is correct
92 Correct 276 ms 22520 KB Output is correct
93 Correct 530 ms 23960 KB Output is correct
94 Correct 504 ms 24184 KB Output is correct
95 Correct 535 ms 24184 KB Output is correct
96 Correct 527 ms 24568 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 70296 KB Output is correct
2 Correct 384 ms 73508 KB Output is correct
3 Execution timed out 2083 ms 109300 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 92532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 20864 KB Output is correct
2 Correct 16 ms 20864 KB Output is correct
3 Correct 15 ms 20864 KB Output is correct
4 Correct 33 ms 21868 KB Output is correct
5 Correct 35 ms 21888 KB Output is correct
6 Correct 33 ms 22008 KB Output is correct
7 Correct 49 ms 23800 KB Output is correct
8 Correct 56 ms 23928 KB Output is correct
9 Correct 55 ms 24056 KB Output is correct
10 Correct 58 ms 23800 KB Output is correct
11 Correct 58 ms 23928 KB Output is correct
12 Correct 56 ms 23928 KB Output is correct
13 Correct 56 ms 24056 KB Output is correct
14 Correct 56 ms 23928 KB Output is correct
15 Correct 57 ms 24056 KB Output is correct
16 Correct 51 ms 23800 KB Output is correct
17 Correct 50 ms 23692 KB Output is correct
18 Correct 58 ms 23800 KB Output is correct
19 Correct 62 ms 23544 KB Output is correct
20 Correct 59 ms 24056 KB Output is correct
21 Correct 55 ms 23928 KB Output is correct
22 Correct 61 ms 24440 KB Output is correct
23 Correct 62 ms 24440 KB Output is correct
24 Correct 67 ms 24824 KB Output is correct
25 Correct 30 ms 23544 KB Output is correct
26 Correct 33 ms 23800 KB Output is correct
27 Correct 30 ms 23168 KB Output is correct
28 Correct 65 ms 24820 KB Output is correct
29 Correct 66 ms 24824 KB Output is correct
30 Correct 67 ms 25016 KB Output is correct
31 Correct 69 ms 24952 KB Output is correct
32 Correct 84 ms 24824 KB Output is correct
33 Correct 79 ms 24824 KB Output is correct
34 Correct 70 ms 24824 KB Output is correct
35 Correct 79 ms 24952 KB Output is correct
36 Correct 27 ms 23316 KB Output is correct
37 Correct 73 ms 24796 KB Output is correct
38 Correct 73 ms 24696 KB Output is correct
39 Correct 75 ms 24824 KB Output is correct
40 Correct 76 ms 24952 KB Output is correct
41 Correct 63 ms 24568 KB Output is correct
42 Correct 61 ms 24436 KB Output is correct
43 Correct 29 ms 23296 KB Output is correct
44 Correct 72 ms 24440 KB Output is correct
45 Correct 66 ms 24568 KB Output is correct
46 Correct 32 ms 23380 KB Output is correct
47 Correct 54 ms 23288 KB Output is correct
48 Correct 43 ms 22776 KB Output is correct
49 Correct 43 ms 22520 KB Output is correct
50 Correct 41 ms 22392 KB Output is correct
51 Correct 37 ms 22248 KB Output is correct
52 Correct 50 ms 23288 KB Output is correct
53 Correct 48 ms 23416 KB Output is correct
54 Correct 52 ms 23288 KB Output is correct
55 Correct 53 ms 23416 KB Output is correct
56 Correct 256 ms 22392 KB Output is correct
57 Correct 267 ms 22268 KB Output is correct
58 Correct 259 ms 22392 KB Output is correct
59 Correct 475 ms 24700 KB Output is correct
60 Correct 550 ms 24824 KB Output is correct
61 Correct 565 ms 25208 KB Output is correct
62 Correct 600 ms 24920 KB Output is correct
63 Correct 572 ms 24896 KB Output is correct
64 Correct 647 ms 25088 KB Output is correct
65 Correct 520 ms 24824 KB Output is correct
66 Correct 621 ms 24824 KB Output is correct
67 Correct 518 ms 24696 KB Output is correct
68 Correct 484 ms 24824 KB Output is correct
69 Correct 454 ms 24312 KB Output is correct
70 Correct 575 ms 24952 KB Output is correct
71 Correct 528 ms 24504 KB Output is correct
72 Correct 563 ms 24976 KB Output is correct
73 Correct 551 ms 24572 KB Output is correct
74 Correct 151 ms 24312 KB Output is correct
75 Correct 174 ms 24540 KB Output is correct
76 Correct 147 ms 23836 KB Output is correct
77 Correct 737 ms 25856 KB Output is correct
78 Correct 731 ms 25852 KB Output is correct
79 Correct 65 ms 24184 KB Output is correct
80 Correct 966 ms 25732 KB Output is correct
81 Correct 909 ms 25876 KB Output is correct
82 Correct 644 ms 25216 KB Output is correct
83 Correct 651 ms 25464 KB Output is correct
84 Correct 123 ms 24104 KB Output is correct
85 Correct 787 ms 25208 KB Output is correct
86 Correct 788 ms 25168 KB Output is correct
87 Correct 146 ms 23928 KB Output is correct
88 Correct 473 ms 23928 KB Output is correct
89 Correct 438 ms 23548 KB Output is correct
90 Correct 408 ms 23432 KB Output is correct
91 Correct 363 ms 22996 KB Output is correct
92 Correct 276 ms 22520 KB Output is correct
93 Correct 530 ms 23960 KB Output is correct
94 Correct 504 ms 24184 KB Output is correct
95 Correct 535 ms 24184 KB Output is correct
96 Correct 527 ms 24568 KB Output is correct
97 Correct 830 ms 70296 KB Output is correct
98 Correct 384 ms 73508 KB Output is correct
99 Execution timed out 2083 ms 109300 KB Time limit exceeded
100 Halted 0 ms 0 KB -