제출 #1000617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1000617		irmuun	함박 스테이크 (JOI20_hamburg)	C++17	1 / 100	1255 ms	1048576 KiB

hamburg

#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";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 1
• Subtask 2: 0 / 1
• Subtask 3: 0 / 3
• Subtask 4: 0 / 6
• Subtask 5: 0 / 1
• Subtask 6: 0 / 3
• Subtask 7: 0 / 6
• Subtask 8: 0 / 79