oj.uz

답안 #282997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
282997 2020-08-25T08:28:13 Z 문홍윤(#5763) Iqea (innopolis2018_final_C) C++17
36 / 100
 2000 ms 108972 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;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 19328 KB Output is correct
2 Correct 14 ms 19328 KB Output is correct
3 Correct 13 ms 19328 KB Output is correct
4 Correct 32 ms 20352 KB Output is correct
5 Correct 33 ms 20352 KB Output is correct
6 Correct 33 ms 20472 KB Output is correct
7 Correct 49 ms 22392 KB Output is correct
8 Correct 61 ms 22520 KB Output is correct
9 Correct 73 ms 22516 KB Output is correct
10 Correct 114 ms 22264 KB Output is correct
11 Correct 66 ms 22392 KB Output is correct
12 Correct 56 ms 22520 KB Output is correct
13 Correct 52 ms 22520 KB Output is correct
14 Correct 54 ms 22392 KB Output is correct
15 Correct 59 ms 22544 KB Output is correct
16 Correct 60 ms 22368 KB Output is correct
17 Correct 57 ms 22136 KB Output is correct
18 Correct 64 ms 22264 KB Output is correct
19 Correct 83 ms 22008 KB Output is correct
20 Correct 61 ms 22520 KB Output is correct
21 Correct 54 ms 22392 KB Output is correct
22 Correct 59 ms 22904 KB Output is correct
23 Correct 58 ms 22904 KB Output is correct
24 Correct 64 ms 23316 KB Output is correct
25 Correct 27 ms 21888 KB Output is correct
26 Correct 35 ms 22272 KB Output is correct
27 Correct 60 ms 21632 KB Output is correct
28 Correct 61 ms 23288 KB Output is correct
29 Correct 65 ms 23284 KB Output is correct
30 Correct 62 ms 23416 KB Output is correct
31 Correct 74 ms 23348 KB Output is correct
32 Correct 77 ms 23288 KB Output is correct
33 Correct 76 ms 23288 KB Output is correct
34 Correct 67 ms 23288 KB Output is correct
35 Correct 76 ms 23416 KB Output is correct
36 Correct 22 ms 21632 KB Output is correct
37 Correct 76 ms 23212 KB Output is correct
38 Correct 83 ms 23288 KB Output is correct
39 Correct 76 ms 23288 KB Output is correct
40 Correct 72 ms 23416 KB Output is correct
41 Correct 58 ms 23032 KB Output is correct
42 Correct 57 ms 22904 KB Output is correct
43 Correct 25 ms 21760 KB Output is correct
44 Correct 67 ms 23032 KB Output is correct
45 Correct 65 ms 22944 KB Output is correct
46 Correct 33 ms 21828 KB Output is correct
47 Correct 52 ms 21752 KB Output is correct
48 Correct 59 ms 21368 KB Output is correct
49 Correct 44 ms 21112 KB Output is correct
50 Correct 51 ms 20984 KB Output is correct
51 Correct 36 ms 20608 KB Output is correct
52 Correct 60 ms 21820 KB Output is correct
53 Correct 45 ms 21912 KB Output is correct
54 Correct 63 ms 21880 KB Output is correct
55 Correct 54 ms 21880 KB Output is correct

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 19328 KB Output is correct
2 Correct 14 ms 19328 KB Output is correct
3 Correct 13 ms 19328 KB Output is correct
4 Correct 32 ms 20352 KB Output is correct
5 Correct 33 ms 20352 KB Output is correct
6 Correct 33 ms 20472 KB Output is correct
7 Correct 49 ms 22392 KB Output is correct
8 Correct 61 ms 22520 KB Output is correct
9 Correct 73 ms 22516 KB Output is correct
10 Correct 114 ms 22264 KB Output is correct
11 Correct 66 ms 22392 KB Output is correct
12 Correct 56 ms 22520 KB Output is correct
13 Correct 52 ms 22520 KB Output is correct
14 Correct 54 ms 22392 KB Output is correct
15 Correct 59 ms 22544 KB Output is correct
16 Correct 60 ms 22368 KB Output is correct
17 Correct 57 ms 22136 KB Output is correct
18 Correct 64 ms 22264 KB Output is correct
19 Correct 83 ms 22008 KB Output is correct
20 Correct 61 ms 22520 KB Output is correct
21 Correct 54 ms 22392 KB Output is correct
22 Correct 59 ms 22904 KB Output is correct
23 Correct 58 ms 22904 KB Output is correct
24 Correct 64 ms 23316 KB Output is correct
25 Correct 27 ms 21888 KB Output is correct
26 Correct 35 ms 22272 KB Output is correct
27 Correct 60 ms 21632 KB Output is correct
28 Correct 61 ms 23288 KB Output is correct
29 Correct 65 ms 23284 KB Output is correct
30 Correct 62 ms 23416 KB Output is correct
31 Correct 74 ms 23348 KB Output is correct
32 Correct 77 ms 23288 KB Output is correct
33 Correct 76 ms 23288 KB Output is correct
34 Correct 67 ms 23288 KB Output is correct
35 Correct 76 ms 23416 KB Output is correct
36 Correct 22 ms 21632 KB Output is correct
37 Correct 76 ms 23212 KB Output is correct
38 Correct 83 ms 23288 KB Output is correct
39 Correct 76 ms 23288 KB Output is correct
40 Correct 72 ms 23416 KB Output is correct
41 Correct 58 ms 23032 KB Output is correct
42 Correct 57 ms 22904 KB Output is correct
43 Correct 25 ms 21760 KB Output is correct
44 Correct 67 ms 23032 KB Output is correct
45 Correct 65 ms 22944 KB Output is correct
46 Correct 33 ms 21828 KB Output is correct
47 Correct 52 ms 21752 KB Output is correct
48 Correct 59 ms 21368 KB Output is correct
49 Correct 44 ms 21112 KB Output is correct
50 Correct 51 ms 20984 KB Output is correct
51 Correct 36 ms 20608 KB Output is correct
52 Correct 60 ms 21820 KB Output is correct
53 Correct 45 ms 21912 KB Output is correct
54 Correct 63 ms 21880 KB Output is correct
55 Correct 54 ms 21880 KB Output is correct
56 Correct 266 ms 21368 KB Output is correct
57 Correct 275 ms 21368 KB Output is correct
58 Correct 266 ms 21496 KB Output is correct
59 Correct 456 ms 23928 KB Output is correct
60 Correct 537 ms 23928 KB Output is correct
61 Correct 496 ms 24312 KB Output is correct
62 Correct 591 ms 23956 KB Output is correct
63 Correct 563 ms 24056 KB Output is correct
64 Correct 634 ms 24312 KB Output is correct
65 Correct 522 ms 24312 KB Output is correct
66 Correct 574 ms 23928 KB Output is correct
67 Correct 547 ms 23904 KB Output is correct
68 Correct 501 ms 24040 KB Output is correct
69 Correct 464 ms 23416 KB Output is correct
70 Correct 601 ms 23928 KB Output is correct
71 Correct 626 ms 23416 KB Output is correct
72 Correct 544 ms 24056 KB Output is correct
73 Correct 528 ms 23928 KB Output is correct
74 Correct 120 ms 23544 KB Output is correct
75 Correct 199 ms 23800 KB Output is correct
76 Correct 178 ms 23032 KB Output is correct
77 Correct 700 ms 25056 KB Output is correct
78 Correct 709 ms 25208 KB Output is correct
79 Correct 57 ms 23164 KB Output is correct
80 Correct 865 ms 25084 KB Output is correct
81 Correct 852 ms 24952 KB Output is correct
82 Correct 631 ms 24568 KB Output is correct
83 Correct 625 ms 24696 KB Output is correct
84 Correct 104 ms 23288 KB Output is correct
85 Correct 770 ms 24696 KB Output is correct
86 Correct 739 ms 24528 KB Output is correct
87 Correct 183 ms 23160 KB Output is correct
88 Correct 486 ms 23160 KB Output is correct
89 Correct 419 ms 22776 KB Output is correct
90 Correct 410 ms 22520 KB Output is correct
91 Correct 362 ms 22136 KB Output is correct
92 Correct 279 ms 21752 KB Output is correct
93 Correct 536 ms 23160 KB Output is correct
94 Correct 430 ms 23288 KB Output is correct
95 Correct 513 ms 23380 KB Output is correct
96 Correct 504 ms 23544 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1049 ms 71124 KB Output is correct
2 Correct 353 ms 71160 KB Output is correct
3 Execution timed out 2062 ms 108972 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2089 ms 92156 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 19328 KB Output is correct
2 Correct 14 ms 19328 KB Output is correct
3 Correct 13 ms 19328 KB Output is correct
4 Correct 32 ms 20352 KB Output is correct
5 Correct 33 ms 20352 KB Output is correct
6 Correct 33 ms 20472 KB Output is correct
7 Correct 49 ms 22392 KB Output is correct
8 Correct 61 ms 22520 KB Output is correct
9 Correct 73 ms 22516 KB Output is correct
10 Correct 114 ms 22264 KB Output is correct
11 Correct 66 ms 22392 KB Output is correct
12 Correct 56 ms 22520 KB Output is correct
13 Correct 52 ms 22520 KB Output is correct
14 Correct 54 ms 22392 KB Output is correct
15 Correct 59 ms 22544 KB Output is correct
16 Correct 60 ms 22368 KB Output is correct
17 Correct 57 ms 22136 KB Output is correct
18 Correct 64 ms 22264 KB Output is correct
19 Correct 83 ms 22008 KB Output is correct
20 Correct 61 ms 22520 KB Output is correct
21 Correct 54 ms 22392 KB Output is correct
22 Correct 59 ms 22904 KB Output is correct
23 Correct 58 ms 22904 KB Output is correct
24 Correct 64 ms 23316 KB Output is correct
25 Correct 27 ms 21888 KB Output is correct
26 Correct 35 ms 22272 KB Output is correct
27 Correct 60 ms 21632 KB Output is correct
28 Correct 61 ms 23288 KB Output is correct
29 Correct 65 ms 23284 KB Output is correct
30 Correct 62 ms 23416 KB Output is correct
31 Correct 74 ms 23348 KB Output is correct
32 Correct 77 ms 23288 KB Output is correct
33 Correct 76 ms 23288 KB Output is correct
34 Correct 67 ms 23288 KB Output is correct
35 Correct 76 ms 23416 KB Output is correct
36 Correct 22 ms 21632 KB Output is correct
37 Correct 76 ms 23212 KB Output is correct
38 Correct 83 ms 23288 KB Output is correct
39 Correct 76 ms 23288 KB Output is correct
40 Correct 72 ms 23416 KB Output is correct
41 Correct 58 ms 23032 KB Output is correct
42 Correct 57 ms 22904 KB Output is correct
43 Correct 25 ms 21760 KB Output is correct
44 Correct 67 ms 23032 KB Output is correct
45 Correct 65 ms 22944 KB Output is correct
46 Correct 33 ms 21828 KB Output is correct
47 Correct 52 ms 21752 KB Output is correct
48 Correct 59 ms 21368 KB Output is correct
49 Correct 44 ms 21112 KB Output is correct
50 Correct 51 ms 20984 KB Output is correct
51 Correct 36 ms 20608 KB Output is correct
52 Correct 60 ms 21820 KB Output is correct
53 Correct 45 ms 21912 KB Output is correct
54 Correct 63 ms 21880 KB Output is correct
55 Correct 54 ms 21880 KB Output is correct
56 Correct 266 ms 21368 KB Output is correct
57 Correct 275 ms 21368 KB Output is correct
58 Correct 266 ms 21496 KB Output is correct
59 Correct 456 ms 23928 KB Output is correct
60 Correct 537 ms 23928 KB Output is correct
61 Correct 496 ms 24312 KB Output is correct
62 Correct 591 ms 23956 KB Output is correct
63 Correct 563 ms 24056 KB Output is correct
64 Correct 634 ms 24312 KB Output is correct
65 Correct 522 ms 24312 KB Output is correct
66 Correct 574 ms 23928 KB Output is correct
67 Correct 547 ms 23904 KB Output is correct
68 Correct 501 ms 24040 KB Output is correct
69 Correct 464 ms 23416 KB Output is correct
70 Correct 601 ms 23928 KB Output is correct
71 Correct 626 ms 23416 KB Output is correct
72 Correct 544 ms 24056 KB Output is correct
73 Correct 528 ms 23928 KB Output is correct
74 Correct 120 ms 23544 KB Output is correct
75 Correct 199 ms 23800 KB Output is correct
76 Correct 178 ms 23032 KB Output is correct
77 Correct 700 ms 25056 KB Output is correct
78 Correct 709 ms 25208 KB Output is correct
79 Correct 57 ms 23164 KB Output is correct
80 Correct 865 ms 25084 KB Output is correct
81 Correct 852 ms 24952 KB Output is correct
82 Correct 631 ms 24568 KB Output is correct
83 Correct 625 ms 24696 KB Output is correct
84 Correct 104 ms 23288 KB Output is correct
85 Correct 770 ms 24696 KB Output is correct
86 Correct 739 ms 24528 KB Output is correct
87 Correct 183 ms 23160 KB Output is correct
88 Correct 486 ms 23160 KB Output is correct
89 Correct 419 ms 22776 KB Output is correct
90 Correct 410 ms 22520 KB Output is correct
91 Correct 362 ms 22136 KB Output is correct
92 Correct 279 ms 21752 KB Output is correct
93 Correct 536 ms 23160 KB Output is correct
94 Correct 430 ms 23288 KB Output is correct
95 Correct 513 ms 23380 KB Output is correct
96 Correct 504 ms 23544 KB Output is correct
97 Correct 1049 ms 71124 KB Output is correct
98 Correct 353 ms 71160 KB Output is correct
99 Execution timed out 2062 ms 108972 KB Time limit exceeded
100 Halted 0 ms 0 KB -