oj.uz

Submission #1000617

# Submission time Handle Problem Language Result Execution time Memory
1000617 2024-06-18T03:57:52 Z irmuun Hamburg Steak (JOI20_hamburg) C++17
1 / 100
 1255 ms 1048576 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,k;
    cin>>n>>k;
    ll l[n+5],d[n+5],r[n+5],u[n+5];
    for(ll i=1;i<=n;i++){
        cin>>l[i]>>d[i]>>r[i]>>u[i];
    }
    vector<ll>adj[n+5],adj_inv[n+5],count(n+5),roots(n+5),order,root_nodes,adj_scc[n+5],com;
    vector<ll>par(n+5),sz(n+5);
    vector<bool>used(n+5);
    function <void(ll)> dfs1=[&](ll x){
        used[x]=1;
        for(auto y:adj[x]){
            if(used[y]==0){
                dfs1(y);
            }
        }
        order.pb(x);
    };
    function <void(ll)> dfs2=[&](ll x){
        used[x]=1;
        com.pb(x);
        for(auto y:adj_inv[x]){
            if(used[y]==0){
                dfs2(y);
            }
        }
    };
    for(ll i=1;i<=n;i++){
        for(ll j=i+1;j<=n;j++){
            if(r[j]<l[i]||r[i]<l[j]||u[i]<d[j]||u[j]<d[i]) continue;
            adj[i].pb(j);
            adj[j].pb(i);
            adj_inv[i].pb(j);
            adj_inv[j].pb(i);
        }
    }
    for(ll i=1;i<=n;i++){
        if(!used[i]){
            dfs1(i);
        }
    }
    fill(all(used),0);
    reverse(all(order));
    for(auto y:order){
        if(!used[y]){
            dfs2(y);
            ll root=com[0];
            for(auto u:com){
                roots[u]=root;
            }
            sz[root]=com.size();
            root_nodes.pb(root);
            com.clear();
        }
    }
    while(root_nodes.size()<k){
        root_nodes.pb(root_nodes[0]);
    }
    for(auto j:root_nodes){
        ll x=1e9,y=1e9;
        for(ll i=1;i<=n;i++){
            if(roots[i]==j){
                x=min(x,r[i]);
                y=min(y,u[i]);
            }
        }
        cout<<x<<' '<<y<<"\n";
    }
}

Compilation message

hamburg.cpp: In function 'int main()':
hamburg.cpp:69:28: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   69 |     while(root_nodes.size()<k){
      |           ~~~~~~~~~~~~~~~~~^~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 63208 KB Output is correct
2 Correct 61 ms 62744 KB Output is correct
3 Correct 62 ms 63248 KB Output is correct
4 Correct 64 ms 63572 KB Output is correct

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 64992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 66312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 67920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 63208 KB Output is correct
2 Correct 61 ms 62744 KB Output is correct
3 Correct 62 ms 63248 KB Output is correct
4 Correct 64 ms 63572 KB Output is correct
5 Runtime error 1255 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 64992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 66312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 67920 KB Output isn't correct
2 Halted 0 ms 0 KB -