oj.uz

Submission #599011

# Submission time Handle Problem Language Result Execution time Memory
599011 2022-07-19T09:03:18 Z 박상훈(#8456) Building Skyscrapers (CEOI19_skyscrapers) C++17
51 / 100
 3500 ms 11960 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Point{
    int x, y, i;
    Point(){}
    Point(int _x, int _y, int _i): x(_x), y(_y), i(_i) {}
    bool operator<(const Point &P) const{
        return tie(x, y) < tie(P.x, P.y);
    }
}a[150150];
vector<int> ans;
map<int, map<int, int>> mp;
bool visited[150150];
int n, dx[8] = {1, -1, 0, 0, 1, 1, -1, -1}, dy[8] = {0, 0, 1, -1, -1, 1, -1, 1};

int bx, by, cnt, b[2020][2020], out[2020][2020], dfn[150150], on[150150], up[150150], cut[150150], ok[150150];

int dfs0(int s){
    visited[s] = 1;
    int ret = 1;
    for (int k=0;k<8;k++){
        int nx = a[s].x + dx[k], ny = a[s].y + dy[k];
        if (mp[nx][ny] && !visited[mp[nx][ny]]){
            ret += dfs0(mp[nx][ny]);
        }
    }
    return ret;
}

void dfs1(int x, int y){
    if (x<0 || x>bx) return;
    if (y<0 || y>by) return;
    if (out[x][y]) return;
    out[x][y] = 1;
    if (b[x][y]) return;

    for (int k=0;k<4;k++){
        int nx = x + dx[k], ny = y + dy[k];
        dfs1(nx, ny);
    }
}

void compress(){
    vector<int> X, Y;
    for (int i=1;i<=n;i++){
        X.push_back(a[i].x);
        Y.push_back(a[i].y);
    }
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    X.erase(unique(X.begin(), X.end()), X.end());
    Y.erase(unique(Y.begin(), Y.end()), Y.end());

    for (int i=1;i<=n;i++){
        a[i].x = lower_bound(X.begin(), X.end(), a[i].x) - X.begin() + 1;
        a[i].y = lower_bound(Y.begin(), Y.end(), a[i].y) - Y.begin() + 1;

        b[a[i].x][a[i].y] = i;
        on[i] = 1;
    }

    bx = X.size() + 1;
    by = Y.size() + 1;

    dfs1(0, 0);
}

void dfs(int x, int y, int pa = -1){
    int s = b[x][y];
    visited[s] = 1;
    dfn[s] = ++cnt;
    up[s] = dfn[s];
    cut[s] = 0;

    int child = 0;

    for (int k=0;k<8;k++){
        int nx = x + dx[k], ny = y + dy[k];
        if (!b[nx][ny] || !on[b[nx][ny]]) continue;
        int nnum = b[nx][ny];

        if (visited[nnum] && nnum!=pa){
            up[s] = min(up[s], dfn[nnum]);
        }
        else if (!visited[nnum]){
            child++;
            dfs(nx, ny, s);
            up[s] = min(up[s], up[nnum]);
            if (up[nnum]>=dfn[s] && pa!=-1) cut[s] = 1;
        }
    }

    if (pa==-1 && child>1) cut[s] = 1;

}

void solve(){
    cnt = 0;
    fill(visited+1, visited+n+1, 0);

    for (int i=1;i<=n;i++) if (on[i]) {dfs(a[i].x, a[i].y); break;}
    for (int i=1;i<=n;i++) assert(visited[i]==on[i]);

    /*for (int i=1;i<=n;i++) printf("%d %d %d / ", on[i], out[a[i].x][a[i].y], cut[i]);
    printf("\n");*/

    for (int i=n;i;i--) if (on[i] && out[a[i].x][a[i].y] && !cut[i]){
        ans.push_back(i);
        on[i] = 0;
        out[a[i].x][a[i].y] = 0;
        b[a[i].x][a[i].y] = 0;
        dfs1(a[i].x, a[i].y);
        return;
    }
    assert(0);
}

int main(){
    int typ;
    scanf("%d %d", &n, &typ);

    for (int i=1;i<=n;i++){
        scanf("%d %d", &a[i].x, &a[i].y);
        a[i].i = i;
        mp[a[i].x][a[i].y] = i;
    }

    if (dfs0(1)!=n) {printf("NO\n"); return 0;}

    compress();
    for (int i=1;i<=n;i++) solve();

    reverse(ans.begin(), ans.end());
    printf("YES\n");
    for (auto &x:ans) printf("%d\n", x);
    return 0;
}

Compilation message

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     scanf("%d %d", &n, &typ);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
skyscrapers.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         scanf("%d %d", &a[i].x, &a[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB ans=YES N=1
2 Correct 0 ms 340 KB ans=YES N=4
3 Correct 0 ms 212 KB ans=NO N=4
4 Correct 0 ms 340 KB ans=YES N=5
5 Correct 1 ms 340 KB ans=YES N=9
6 Correct 1 ms 340 KB ans=YES N=5
7 Correct 1 ms 212 KB ans=NO N=9
8 Correct 0 ms 212 KB ans=NO N=10
9 Correct 1 ms 340 KB ans=YES N=10
10 Correct 1 ms 340 KB ans=YES N=10
11 Correct 0 ms 340 KB ans=YES N=10
12 Correct 0 ms 340 KB ans=YES N=9
13 Correct 0 ms 340 KB ans=YES N=9
14 Correct 0 ms 340 KB ans=YES N=8
15 Correct 0 ms 340 KB ans=YES N=8
16 Correct 1 ms 212 KB ans=NO N=2

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB ans=YES N=1
2 Correct 0 ms 340 KB ans=YES N=4
3 Correct 0 ms 212 KB ans=NO N=4
4 Correct 0 ms 340 KB ans=YES N=5
5 Correct 1 ms 340 KB ans=YES N=9
6 Correct 1 ms 340 KB ans=YES N=5
7 Correct 1 ms 212 KB ans=NO N=9
8 Correct 0 ms 212 KB ans=NO N=10
9 Correct 1 ms 340 KB ans=YES N=10
10 Correct 1 ms 340 KB ans=YES N=10
11 Correct 0 ms 340 KB ans=YES N=10
12 Correct 0 ms 340 KB ans=YES N=9
13 Correct 0 ms 340 KB ans=YES N=9
14 Correct 0 ms 340 KB ans=YES N=8
15 Correct 0 ms 340 KB ans=YES N=8
16 Correct 1 ms 212 KB ans=NO N=2
17 Correct 1 ms 340 KB ans=YES N=17
18 Correct 1 ms 340 KB ans=YES N=25
19 Correct 1 ms 468 KB ans=YES N=100
20 Correct 2 ms 468 KB ans=YES N=185
21 Correct 0 ms 340 KB ans=NO N=174
22 Correct 1 ms 596 KB ans=YES N=90
23 Correct 1 ms 340 KB ans=YES N=63
24 Correct 1 ms 340 KB ans=YES N=87
25 Correct 1 ms 468 KB ans=YES N=183
26 Correct 2 ms 468 KB ans=YES N=188
27 Correct 1 ms 468 KB ans=YES N=183
28 Correct 1 ms 468 KB ans=YES N=189
29 Correct 2 ms 468 KB ans=YES N=200
30 Correct 1 ms 468 KB ans=YES N=190
31 Correct 2 ms 468 KB ans=YES N=187
32 Correct 2 ms 684 KB ans=YES N=187
33 Correct 1 ms 596 KB ans=YES N=182
34 Correct 2 ms 724 KB ans=YES N=184
35 Correct 2 ms 852 KB ans=YES N=188
36 Correct 1 ms 724 KB ans=YES N=181
37 Correct 1 ms 724 KB ans=YES N=188
38 Correct 2 ms 980 KB ans=YES N=191
39 Correct 1 ms 468 KB ans=YES N=196
40 Correct 1 ms 468 KB ans=YES N=196
41 Correct 1 ms 468 KB ans=YES N=196
42 Correct 1 ms 468 KB ans=YES N=196
43 Correct 1 ms 724 KB ans=YES N=195

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB ans=YES N=1
2 Correct 0 ms 340 KB ans=YES N=4
3 Correct 0 ms 212 KB ans=NO N=4
4 Correct 0 ms 340 KB ans=YES N=5
5 Correct 1 ms 340 KB ans=YES N=9
6 Correct 1 ms 340 KB ans=YES N=5
7 Correct 1 ms 212 KB ans=NO N=9
8 Correct 0 ms 212 KB ans=NO N=10
9 Correct 1 ms 340 KB ans=YES N=10
10 Correct 1 ms 340 KB ans=YES N=10
11 Correct 0 ms 340 KB ans=YES N=10
12 Correct 0 ms 340 KB ans=YES N=9
13 Correct 0 ms 340 KB ans=YES N=9
14 Correct 0 ms 340 KB ans=YES N=8
15 Correct 0 ms 340 KB ans=YES N=8
16 Correct 1 ms 212 KB ans=NO N=2
17 Correct 1 ms 340 KB ans=YES N=17
18 Correct 1 ms 340 KB ans=YES N=25
19 Correct 1 ms 468 KB ans=YES N=100
20 Correct 2 ms 468 KB ans=YES N=185
21 Correct 0 ms 340 KB ans=NO N=174
22 Correct 1 ms 596 KB ans=YES N=90
23 Correct 1 ms 340 KB ans=YES N=63
24 Correct 1 ms 340 KB ans=YES N=87
25 Correct 1 ms 468 KB ans=YES N=183
26 Correct 2 ms 468 KB ans=YES N=188
27 Correct 1 ms 468 KB ans=YES N=183
28 Correct 1 ms 468 KB ans=YES N=189
29 Correct 2 ms 468 KB ans=YES N=200
30 Correct 1 ms 468 KB ans=YES N=190
31 Correct 2 ms 468 KB ans=YES N=187
32 Correct 2 ms 684 KB ans=YES N=187
33 Correct 1 ms 596 KB ans=YES N=182
34 Correct 2 ms 724 KB ans=YES N=184
35 Correct 2 ms 852 KB ans=YES N=188
36 Correct 1 ms 724 KB ans=YES N=181
37 Correct 1 ms 724 KB ans=YES N=188
38 Correct 2 ms 980 KB ans=YES N=191
39 Correct 1 ms 468 KB ans=YES N=196
40 Correct 1 ms 468 KB ans=YES N=196
41 Correct 1 ms 468 KB ans=YES N=196
42 Correct 1 ms 468 KB ans=YES N=196
43 Correct 1 ms 724 KB ans=YES N=195
44 Correct 1 ms 596 KB ans=NO N=1934
45 Correct 1 ms 340 KB ans=NO N=1965
46 Correct 73 ms 1032 KB ans=YES N=1824
47 Correct 96 ms 1136 KB ans=YES N=1981
48 Correct 73 ms 1104 KB ans=YES N=1814
49 Correct 89 ms 1300 KB ans=YES N=1854
50 Correct 77 ms 1024 KB ans=YES N=1831
51 Correct 92 ms 1132 KB ans=YES N=2000
52 Correct 91 ms 1296 KB ans=YES N=1847
53 Correct 84 ms 1364 KB ans=YES N=1819
54 Correct 88 ms 1068 KB ans=YES N=1986
55 Correct 102 ms 1852 KB ans=YES N=2000
56 Correct 78 ms 6312 KB ans=YES N=1834
57 Correct 90 ms 2576 KB ans=YES N=1860
58 Correct 85 ms 3236 KB ans=YES N=1898
59 Correct 84 ms 2004 KB ans=YES N=1832
60 Correct 81 ms 6188 KB ans=YES N=1929
61 Correct 94 ms 1624 KB ans=YES N=1919
62 Correct 94 ms 2672 KB ans=YES N=1882
63 Correct 78 ms 10020 KB ans=YES N=1922
64 Correct 91 ms 6556 KB ans=YES N=1989
65 Correct 51 ms 876 KB ans=YES N=1978
66 Correct 102 ms 11732 KB ans=YES N=1867
67 Correct 108 ms 1760 KB ans=YES N=1942

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB ans=NO N=1934
2 Correct 1 ms 340 KB ans=NO N=1965
3 Correct 71 ms 1032 KB ans=YES N=1824
4 Correct 87 ms 1132 KB ans=YES N=1981
5 Correct 73 ms 1044 KB ans=YES N=1814
6 Correct 88 ms 1332 KB ans=YES N=1854
7 Correct 77 ms 1056 KB ans=YES N=1831
8 Correct 92 ms 1180 KB ans=YES N=2000
9 Correct 95 ms 1236 KB ans=YES N=1847
10 Correct 84 ms 1428 KB ans=YES N=1819
11 Correct 92 ms 1108 KB ans=YES N=1986
12 Correct 99 ms 1896 KB ans=YES N=2000
13 Correct 78 ms 6356 KB ans=YES N=1834
14 Correct 81 ms 2628 KB ans=YES N=1860
15 Correct 85 ms 3284 KB ans=YES N=1898
16 Correct 84 ms 2004 KB ans=YES N=1832
17 Correct 76 ms 6228 KB ans=YES N=1929
18 Correct 99 ms 1620 KB ans=YES N=1919
19 Correct 96 ms 2720 KB ans=YES N=1882
20 Correct 83 ms 10060 KB ans=YES N=1922
21 Correct 99 ms 6600 KB ans=YES N=1989
22 Correct 53 ms 908 KB ans=YES N=1978
23 Correct 88 ms 11740 KB ans=YES N=1867

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB ans=YES N=1
2 Correct 0 ms 340 KB ans=YES N=4
3 Correct 0 ms 212 KB ans=NO N=4
4 Correct 0 ms 340 KB ans=YES N=5
5 Correct 1 ms 340 KB ans=YES N=9
6 Correct 1 ms 340 KB ans=YES N=5
7 Correct 1 ms 212 KB ans=NO N=9
8 Correct 0 ms 212 KB ans=NO N=10
9 Correct 1 ms 340 KB ans=YES N=10
10 Correct 1 ms 340 KB ans=YES N=10
11 Correct 0 ms 340 KB ans=YES N=10
12 Correct 0 ms 340 KB ans=YES N=9
13 Correct 0 ms 340 KB ans=YES N=9
14 Correct 0 ms 340 KB ans=YES N=8
15 Correct 0 ms 340 KB ans=YES N=8
16 Correct 1 ms 212 KB ans=NO N=2
17 Correct 1 ms 340 KB ans=YES N=17
18 Correct 1 ms 340 KB ans=YES N=25
19 Correct 1 ms 468 KB ans=YES N=100
20 Correct 2 ms 468 KB ans=YES N=185
21 Correct 0 ms 340 KB ans=NO N=174
22 Correct 1 ms 596 KB ans=YES N=90
23 Correct 1 ms 340 KB ans=YES N=63
24 Correct 1 ms 340 KB ans=YES N=87
25 Correct 1 ms 468 KB ans=YES N=183
26 Correct 2 ms 468 KB ans=YES N=188
27 Correct 1 ms 468 KB ans=YES N=183
28 Correct 1 ms 468 KB ans=YES N=189
29 Correct 2 ms 468 KB ans=YES N=200
30 Correct 1 ms 468 KB ans=YES N=190
31 Correct 2 ms 468 KB ans=YES N=187
32 Correct 2 ms 684 KB ans=YES N=187
33 Correct 1 ms 596 KB ans=YES N=182
34 Correct 2 ms 724 KB ans=YES N=184
35 Correct 2 ms 852 KB ans=YES N=188
36 Correct 1 ms 724 KB ans=YES N=181
37 Correct 1 ms 724 KB ans=YES N=188
38 Correct 2 ms 980 KB ans=YES N=191
39 Correct 1 ms 468 KB ans=YES N=196
40 Correct 1 ms 468 KB ans=YES N=196
41 Correct 1 ms 468 KB ans=YES N=196
42 Correct 1 ms 468 KB ans=YES N=196
43 Correct 1 ms 724 KB ans=YES N=195
44 Correct 1 ms 596 KB ans=NO N=1934
45 Correct 1 ms 340 KB ans=NO N=1965
46 Correct 73 ms 1032 KB ans=YES N=1824
47 Correct 96 ms 1136 KB ans=YES N=1981
48 Correct 73 ms 1104 KB ans=YES N=1814
49 Correct 89 ms 1300 KB ans=YES N=1854
50 Correct 77 ms 1024 KB ans=YES N=1831
51 Correct 92 ms 1132 KB ans=YES N=2000
52 Correct 91 ms 1296 KB ans=YES N=1847
53 Correct 84 ms 1364 KB ans=YES N=1819
54 Correct 88 ms 1068 KB ans=YES N=1986
55 Correct 102 ms 1852 KB ans=YES N=2000
56 Correct 78 ms 6312 KB ans=YES N=1834
57 Correct 90 ms 2576 KB ans=YES N=1860
58 Correct 85 ms 3236 KB ans=YES N=1898
59 Correct 84 ms 2004 KB ans=YES N=1832
60 Correct 81 ms 6188 KB ans=YES N=1929
61 Correct 94 ms 1624 KB ans=YES N=1919
62 Correct 94 ms 2672 KB ans=YES N=1882
63 Correct 78 ms 10020 KB ans=YES N=1922
64 Correct 91 ms 6556 KB ans=YES N=1989
65 Correct 51 ms 876 KB ans=YES N=1978
66 Correct 102 ms 11732 KB ans=YES N=1867
67 Correct 108 ms 1760 KB ans=YES N=1942
68 Correct 120 ms 9804 KB ans=NO N=66151
69 Correct 31 ms 4180 KB ans=NO N=64333
70 Execution timed out 3561 ms 11948 KB Time limit exceeded
71 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 9792 KB ans=NO N=66151
2 Correct 31 ms 4120 KB ans=NO N=64333
3 Execution timed out 3575 ms 11960 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB ans=NO N=1934
2 Correct 1 ms 340 KB ans=NO N=1965
3 Correct 71 ms 1032 KB ans=YES N=1824
4 Correct 87 ms 1132 KB ans=YES N=1981
5 Correct 73 ms 1044 KB ans=YES N=1814
6 Correct 88 ms 1332 KB ans=YES N=1854
7 Correct 77 ms 1056 KB ans=YES N=1831
8 Correct 92 ms 1180 KB ans=YES N=2000
9 Correct 95 ms 1236 KB ans=YES N=1847
10 Correct 84 ms 1428 KB ans=YES N=1819
11 Correct 92 ms 1108 KB ans=YES N=1986
12 Correct 99 ms 1896 KB ans=YES N=2000
13 Correct 78 ms 6356 KB ans=YES N=1834
14 Correct 81 ms 2628 KB ans=YES N=1860
15 Correct 85 ms 3284 KB ans=YES N=1898
16 Correct 84 ms 2004 KB ans=YES N=1832
17 Correct 76 ms 6228 KB ans=YES N=1929
18 Correct 99 ms 1620 KB ans=YES N=1919
19 Correct 96 ms 2720 KB ans=YES N=1882
20 Correct 83 ms 10060 KB ans=YES N=1922
21 Correct 99 ms 6600 KB ans=YES N=1989
22 Correct 53 ms 908 KB ans=YES N=1978
23 Correct 88 ms 11740 KB ans=YES N=1867
24 Correct 105 ms 9792 KB ans=NO N=66151
25 Correct 31 ms 4120 KB ans=NO N=64333
26 Execution timed out 3575 ms 11960 KB Time limit exceeded
27 Halted 0 ms 0 KB -