제출 #728443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
728443		WKYH	Rainforest Jumps (APIO21_jumps)	C++14	33 / 100	4059 ms	4368 KiB

jumps

#include<bits/stdc++.h>
#define qc ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rt return
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vecin(a) for(auto &d:a)cin>>d;
typedef long long int ll;
const long long mod=1e9+7;
const int int_inf=2147483647;
const long long int ll_inf=9223372036854775807;
const int alp_up=64;
const int alp_lw=96;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
using namespace std;
ll gcd(ll a,ll b){if(b==0)rt a;rt gcd(b,a%b);}
ll lcm(ll a,ll b){rt a/gcd(a,b)*b;}
void setIO(string name)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}

//*
int n;
vector<int>l,r;
void init(int N,vector<int>h)
{
    n=N;
    l.resize(n,-1);
    r.resize(n,-1);
    stack<int>s;
    for(int i=0;i<n;i++)
    {
        while(!s.empty()&&h[s.top()]<h[i])s.pop();
        if(!s.empty())l[i]=s.top();
        s.push(i);
    }
    for(int i=n-1;i>=0;i--)
    {
        while(h[s.top()]<h[i])s.pop();
        if(!s.empty())r[i]=s.top();
        s.push(i);
    }
    //for(auto c:l)cout<<c<<" ";cout<<"\n";
    //for(auto c:r)cout<<c<<" ";cout<<"\n";
}
int minimum_jumps(int a,int b,int c,int d)
{
    queue<pair<int,int>>q;
    vector<bool>vis(n,0);
    for(int i=a;i<=b;i++){
        q.push({i,0});
    }
    while(!q.empty()){
        int x=q.front().first,y=q.front().second;
        q.pop();
        //cout<<x<<" ";
        if(c<=x&&x<=d)rt y;
        if(l[x]!=-1&&!vis[l[x]]){
            q.push({l[x],y+1});
            vis[l[x]]=1;
        }
        if(r[x]!=-1&&!vis[r[x]]){
            q.push({r[x],y+1});
            vis[r[x]]=1;
        }
    }
    rt -1;
}

int xmain()
{
    init(7, {3, 2, 1, 6, 4, 5, 7});
    cout<<minimum_jumps(4, 4, 6, 6)<<" "<<minimum_jumps(1, 3, 5, 6)<<" "<<minimum_jumps(0, 1, 2, 2);
    rt 0;
}
/*/

int n,k;
vector<pair<ll,int>>age;
vector<vector<pair<int,ll>>>edge;
vector<ll>ans;
//vector<bool>vis;
bool comp(pair<ll,int>a,pair<ll,int>b){rt a.se<b.se;}
int main()
{
    cin>>n>>k;
    age.resize(n);
    edge.resize(n);
    //vis.resize(n,0);
    ans.resize(n,ll_inf);
    for(int i=0;i<n;i++){
        cin>>age[i].first;
        age[i].second=i;
    }
    for(int i=0;i<k;i++){
        int u,v;cin>>u>>v;
        u--;v--;
        edge[u].push_back({v,0});
        edge[v].push_back({u,0});
    }
    sort(all(age));
    for(int i=0;i<n-1;i++){
        edge[age[i].second].push_back({age[i+1].second,abs(age[i].first-age[i+1].first)});
        edge[age[i+1].second].push_back({age[i].second,abs(age[i].first-age[i+1].first)});
    }
    ans[0]=0;
    priority_queue<pair<ll,int>>q;
    q.push({-ans[0],0});
    while(!q.empty()){
        int u=-q.top().first,v=q.top().second;
        q.pop();
        //if(vis[v])continue;
        //vis[v]=1;
        for(auto c:edge[v]){
            if(ans[c.fi]>ans[v]+c.se){
                ans[c.fi]=ans[v]+c.se;
                q.push({-ans[c.fi],c.fi});
            }
        }
    }


    for(auto c:ans)cout<<c<<" ";
}

//*/

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

jumps.cpp: In function 'void setIO(std::string)':
jumps.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19