CSES - NOI 2024 - Results
Submission details
Task:Thin Ice
Sender:Sofie Fu
Submission time:2024-03-14 23:19:19 +0200
Language:C++ (C++20)
Status:READY
Result:12
Feedback
groupverdictscore
#10
#2ACCEPTED12
#30
#40
#50
#60
Test results
testverdicttimegroup
#10.00 s1, 5, 6details
#20.00 s1, 5, 6details
#30.00 s1, 5, 6details
#40.00 s1, 5, 6details
#50.00 s1, 5, 6details
#6ACCEPTED0.00 s1, 5, 6details
#70.00 s1, 5, 6details
#80.00 s1, 5, 6details
#9ACCEPTED0.00 s1, 2, 5, 6details
#10ACCEPTED0.20 s2, 6details
#11ACCEPTED0.07 s2, 6details
#12ACCEPTED0.18 s2, 6details
#13ACCEPTED0.06 s2, 6details
#14ACCEPTED0.07 s2, 6details
#15ACCEPTED0.13 s2, 6details
#16ACCEPTED0.13 s2, 6details
#17ACCEPTED0.17 s2, 6details
#18ACCEPTED0.17 s2, 6details
#19ACCEPTED0.06 s2, 6details
#20ACCEPTED0.07 s2, 6details
#21ACCEPTED0.04 s2, 6details
#220.00 s3, 4, 5, 6details
#230.00 s3, 4, 5, 6details
#240.00 s3, 4, 5, 6details
#25ACCEPTED0.00 s3, 4, 5, 6details
#260.00 s3, 4, 5, 6details
#270.00 s3, 4, 5, 6details
#280.30 s4, 6details
#290.16 s4, 6details
#300.16 s4, 6details
#310.18 s4, 6details
#32ACCEPTED0.05 s4, 6details
#330.15 s4, 6details
#340.34 s4, 6details
#350.01 s5, 6details
#360.00 s5, 6details
#370.01 s5, 6details
#380.00 s5, 6details
#39ACCEPTED0.00 s5, 6details
#400.01 s5, 6details
#410.01 s5, 6details
#420.43 s6details
#430.42 s6details
#440.31 s6details
#450.25 s6details
#46ACCEPTED0.05 s6details
#470.34 s6details
#480.49 s6details

Compiler report

input/code.cpp: In constructor 'dsu::dsu(long long int)':
input/code.cpp:46:18: warning: 'dsu::nei' will be initialized after [-Wreorder]
   46 |     vo<set<int>> nei;
      |                  ^~~
input/code.cpp:45:23: warning:   'vi dsu::conEdge' [-Wreorder]
   45 |     vi par, siz, val, conEdge;
      |                       ^~~~~~~
input/code.cpp:47:5: warning:   when initialized here [-Wreorder]
   47 |     dsu(int n): par(n), siz(n, 1), val(n), nei(n), conEdge(n, 0){
      |     ^~~

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vo vector
#define pb push_back
#define se second
#define fi first
#define sz(x) x.size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define umap unordered_map
#define uset unordered_set

#define rep(i, a, b) for(ll i=(a); i<b; i++)
#define pr1(x) cerr << #x << '=' << x << ' ';
//for google contests
#define all(v) v.begin(), v.end()
#define repd(i, a, b) for(ll i=(b-1); i >= a; i--)
void _pr(signed x) {cerr << x;}
void _pr(long long x) {cerr << x;}
void _pr(unsigned long long x) {cerr << x;}
void _pr(double x) {cerr << x;}
void _pr(char x) {cerr << '\'' << x << '\'';}
void _pr(const char* x) {cerr << x;}
void _pr(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V> void _pr(const pair<T, V> &x);
template<typename T, typename V> void _pr(const pair<T, V> &x) {cerr << "\e[95m" << "[ "; _pr(x.first); cerr << ", "; _pr(x.second); cerr << "\e[95m" << ']';}
template<typename T> void _pr(const T &x) {int F=0; cerr << '{'; for(auto &i: x) cerr << (F++ ? ", " : ""), _pr(i); cerr << "\e[91m" << '}';}
template <typename T, typename... V> void _pr(T t, V... v) {_pr(t); if(sizeof...(v)) cerr << ", "; _pr(v...);}
#define pr(x...) cerr << "\e[91m" << __func__ << ':' << __LINE__ << " [" << #x << "] = ["; _pr(x); cerr << "\e[91m" << ']' << "\033[0m"  << endl;

//go for outline with ;, then details
ll const inf = LLONG_MAX, mxn = 2e5+4;
int r, c, ans;
pii dp[mxn];
vo<vi> tbl;
map<int, set<int>> order; //all comps of val=key;

int compress(int a, int b){
    return a*c + b;
}

struct dsu{
    vi par, siz, val, conEdge;
    vo<set<int>> nei;
    dsu(int n): par(n), siz(n, 1), val(n), nei(n), conEdge(n, 0){
        rep(i, 0, n) par[i] = i;
    }
    int findpar(int v){
        if(v==par[v]) return v;
        return par[v] = findpar(par[v]);
    }
    void unite(int a, int b){
        a = findpar(a), b = findpar(b);
        if(a!=b){
            if(siz[b] > siz[a]) swap(a, b);
            par[b] = a;
            siz[a] += siz[b]; siz[b] = 0;
            conEdge[a] |= conEdge[b];
        }
    }
};
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool ir(int a, int b){
    return a>=0&&b>=0&&a<r&&b<c;
}
bool walk(int a, int b, int val){
    priority_queue<array<int, 3>> pq;
    pq.push({tbl[a][b], a, b});
    int target = val;
    vo<vi> vis(r, vi(c, 0));
    while(pq.size()){
        auto [val, a, b] = pq.top(); pq.pop();
        if(vis[a][b]) continue;
        if(val < target) return 0;

        vis[a][b] = 1;
        target--;
        if(target<=0) return 1;

        for(auto x: dir){
            int nr = x[0]+a, nc = x[1]+b;
            if(ir(nr, nc) && !vis[nr][nc]){
                pq.push({tbl[nr][nc], nr, nc});
            }
        }
    }
    return 0;
}

// bool f(int val){
//     dsu g(r*c);
//     for(auto [i, u]: kant){
//         if(walk(i, u, val)) return 1;
//     }
//     return 0;
// }

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>r>>c; 
    tbl.assign(r, vi(c, 0));
    dsu g(r*c);
    rep(i, 0, r){
        rep(u, 0, c){
            cin>>tbl[i][u];
            if(i==0 || u==0 || i==r-1 || u==c-1) g.conEdge[compress(i, u)] = 1;
        }
    }

    rep(i, 0, r){
        rep(u, 0, c){
            for(auto [nr, nc]: dir){
                nr+=i, nc+=u;
                if(ir(nr, nc) && tbl[i][u] == tbl[nr][nc]){
                    g.unite(compress(nr, nc), compress(i, u));
                }
            }
        }
    }
    rep(i, 0, r){
        rep(u, 0, c){
            int b = compress(i, u); b=g.findpar(b); g.val[b] = tbl[i][u];
            order[tbl[i][u]].insert(b);
            for(auto [nr, nc]: dir){
                nr+=i, nc+=u;
                if(ir(nr, nc)){
                    int a = compress(nr, nc);
                    a = g.findpar(a);
                    if(tbl[i][u] <= tbl[nr][nc]){
                        g.nei[a].insert(b); 

                    }
                    else if(tbl[nr][nc] >= tbl[i][u]){
                        g.nei[b].insert(a);
                    }
                }
            }
        }
    }

    for(auto size: order){
        for(auto x: size.se){ //x should already be comp par?
            for(auto neigh: g.nei[x]){
                pii pre = dp[neigh]; //tmp and max connected to edge
                dp[x].fi = max(dp[x].fi, min(g.val[x], pre.fi + g.siz[x]));

                dp[x].se = max(pre.se, dp[x].se);
                if(g.conEdge[x]) dp[x].se = g.val[x];
                ans = max(ans, min(dp[x].se, dp[x].fi));
            }
        }
    }

    cout << ans;

    // int lo = 0, hi = 2e5+4;
    // while(hi-lo>1){
    //     int mid = (hi+lo)/2;
    //     if(f(mid)) lo = mid;
    //     else hi = mid;
    // }
    // cout << lo;
}

Test details

Test 1

Group: 1, 5, 6

Verdict:

input
4 4
9 11 5 7
7 9 14 3
1 3 2 3
11 4 14 8

correct output
10

user output
5

Test 2

Group: 1, 5, 6

Verdict:

input
5 3
10 7 11
8 5 5
12 9 10
3 13 9
...

correct output
10

user output
6

Test 3

Group: 1, 5, 6

Verdict:

input
4 4
3 2 2 2
5 1 1 1
8 4 1 1
7 6 2 1

correct output
8

user output
5

Test 4

Group: 1, 5, 6

Verdict:

input
3 5
1 11 1 3 5
4 12 7 8 7
13 14 14 9 4

correct output
14

user output
7

Test 5

Group: 1, 5, 6

Verdict:

input
5 3
11 8 12
11 11 12
6 2 3
11 8 13
...

correct output
12

user output
10

Test 6

Group: 1, 5, 6

Verdict: ACCEPTED

input
3 5
14 14 14 14 14
14 14 14 14 14
14 14 14 14 14

correct output
14

user output
14

Test 7

Group: 1, 5, 6

Verdict:

input
4 4
12 8 6 5
12 9 6 1
10 1 3 2
8 1 1 1

correct output
12

user output
10

Test 8

Group: 1, 5, 6

Verdict:

input
4 4
8 3 15 14
10 12 2 4
5 16 9 6
7 13 1 11

correct output
13

user output
4

Test 9

Group: 1, 2, 5, 6

Verdict: ACCEPTED

input
4 4
4 1 1 2
3 5 4 2
2 2 1 2
1 4 3 4

correct output
4

user output
4

Test 10

Group: 2, 6

Verdict: ACCEPTED

input
10 20000
5 3 2 1 3 2 3 3 4 5 1 1 2 3 5 ...

correct output
5

user output
5

Test 11

Group: 2, 6

Verdict: ACCEPTED

input
10 20000
1 2 1 2 1 2 1 2 1 1 1 1 2 1 1 ...

correct output
3

user output
3

Test 12

Group: 2, 6

Verdict: ACCEPTED

input
10 20000
3 2 2 3 1 2 1 4 4 3 1 4 3 2 4 ...

correct output
5

user output
5

Test 13

Group: 2, 6

Verdict: ACCEPTED

input
20000 10
1 1 3 1 2 1 1 1 1 1
1 2 2 1 1 1 1 2 1 1
2 1 1 1 2 2 1 1 1 2
1 1 1 1 1 1 1 1 1 1
...

correct output
4

user output
4

Test 14

Group: 2, 6

Verdict: ACCEPTED

input
10 20000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
3

user output
3

Test 15

Group: 2, 6

Verdict: ACCEPTED

input
10 20000
3 1 3 1 2 1 2 3 2 2 1 2 1 1 2 ...

correct output
3

user output
3

Test 16

Group: 2, 6

Verdict: ACCEPTED

input
10 20000
1 2 2 2 1 2 3 1 2 2 2 1 2 2 2 ...

correct output
4

user output
4

Test 17

Group: 2, 6

Verdict: ACCEPTED

input
10 20000
3 3 2 3 2 3 2 2 2 2 2 1 3 2 1 ...

correct output
4

user output
4

Test 18

Group: 2, 6

Verdict: ACCEPTED

input
10 20000
1 3 3 1 1 4 3 3 3 1 2 2 1 3 1 ...

correct output
5

user output
5

Test 19

Group: 2, 6

Verdict: ACCEPTED

input
7 28571
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

correct output
3

user output
3

Test 20

Group: 2, 6

Verdict: ACCEPTED

input
28571 7
4 4 4 4 4 4 4
4 4 4 4 4 4 4
4 4 4 4 4 4 4
4 4 4 4 4 4 4
...

correct output
5

user output
5

Test 21

Group: 2, 6

Verdict: ACCEPTED

input
447 447
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...

correct output
3

user output
3

Test 22

Group: 3, 4, 5, 6

Verdict:

input
1 100
46 23 23 55 37 17 30 32 25 71 ...

correct output
30

user output
4

Test 23

Group: 3, 4, 5, 6

Verdict:

input
1 100
8 13 12 11 15 15 15 19 18 21 2...

correct output
76

user output
11

Test 24

Group: 3, 4, 5, 6

Verdict:

input
1 100
94 94 94 95 95 91 97 100 92 98...

correct output
95

user output
12

Test 25

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
1 100
83 83 83 83 83 83 83 83 83 83 ...

correct output
83

user output
83

Test 26

Group: 3, 4, 5, 6

Verdict:

input
1 100
33 34 35 38 38 40 41 42 42 45 ...

correct output
95

user output
44

Test 27

Group: 3, 4, 5, 6

Verdict:

input
1 100
57 1 80 39 18 63 30 86 85 55 8...

correct output
29

user output
3

Test 28

Group: 4, 6

Verdict:

input
1 200000
138736 14949 12344 104147 1333...

correct output
1806

user output
9

Test 29

Group: 4, 6

Verdict:

input
1 200000
141245 141090 141163 141286 14...

correct output
155109

user output
10

Test 30

Group: 4, 6

Verdict:

input
1 200000
102358 102469 102440 102402 10...

correct output
152388

user output
9

Test 31

Group: 4, 6

Verdict:

input
1 200000
180410 160820 160820 180614 18...

correct output
160832

user output
30

Test 32

Group: 4, 6

Verdict: ACCEPTED

input
1 200000
198270 198270 198270 198270 19...

correct output
198270

user output
198270

Test 33

Group: 4, 6

Verdict:

input
1 200000
1 1 3 2 1 1 2 3 6 6 6 7 8 9 10...

correct output
199995

user output
494

Test 34

Group: 4, 6

Verdict:

input
1 200000
14737 162555 44228 170991 1340...

correct output
1902

user output
8

Test 35

Group: 5, 6

Verdict:

input
31 32
669 792 226 189 860 737 291 83...

correct output
565

user output
9

Test 36

Group: 5, 6

Verdict:

input
10 100
730 698 339 743 536 702 94 556...

correct output
529

user output
10

Test 37

Group: 5, 6

Verdict:

input
32 31
633 613 618 605 635 638 668 67...

correct output
678

user output
45

Test 38

Group: 5, 6

Verdict:

input
142 7
983 930 963 926 979 962 962
966 930 963 924 928 928 926
926 929 929 922 931 931 978
929 929 929 922 959 928 964
...

correct output
934

user output
68

Test 39

Group: 5, 6

Verdict: ACCEPTED

input
31 32
977 977 977 977 977 977 977 97...

correct output
977

user output
977

Test 40

Group: 5, 6

Verdict:

input
50 20
1 27 14 23 38 48 56 3 12 9 6 2...

correct output
997

user output
104

Test 41

Group: 5, 6

Verdict:

input
20 50
481 532 624 290 965 58 448 872...

correct output
504

user output
9

Test 42

Group: 6

Verdict:

input
447 447
6474 27185 108482 124481 16058...

correct output
88202

user output
10

Test 43

Group: 6

Verdict:

input
1000 200
27722 57131 197677 184858 9285...

correct output
89324

user output
10

Test 44

Group: 6

Verdict:

input
447 447
70928 73154 72640 74764 75237 ...

correct output
181096

user output
171

Test 45

Group: 6

Verdict:

input
7 28571
193031 185883 171670 185794 17...

correct output
171680

user output
84

Test 46

Group: 6

Verdict: ACCEPTED

input
10 20000
191628 191628 191628 191628 19...

correct output
191628

user output
191628

Test 47

Group: 6

Verdict:

input
200 1000
3550 2640 3791 4248 4257 4504 ...

correct output
199997

user output
1009

Test 48

Group: 6

Verdict:

input
1000 200
198379 62425 88013 50967 49098...

correct output
89131

user output
11