Submission #586406

#	Time	Username	Problem	Language	Result	Execution time	Memory
586406		krit3379	Journey (NOI18_journey)	C++17	69 / 100	2036 ms	35516 KiB

journey

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 10005

int ord[N];

struct A{
    int a,w;
    bool operator<(const A& o)const{
        if(w!=o.w)return w>o.w;
        return ord[a]>ord[o.a];
    }
};

int deg[N],dis[405][N],num;
bitset<N> vis[405];
vector<A> g[N];
queue<int> t;
priority_queue<A> q;

int main(){
    int n,m,h,i,j,a,w;
    scanf("%d %d %d",&n,&m,&h);
    for(i=0;i<n-1;i++){
        for(j=0;j<h;j++){
            scanf("%d %d",&a,&w);
            if(a<=i)continue;
            g[i].push_back({a,w});
            if(!w)deg[a]++;
        }
    }
    for(i=0;i<n;i++)if(!deg[i])t.push(i);
    num=0;
    while(!t.empty()){
        auto a=t.front();
        t.pop();
        ord[a]=num++;
        for(auto [x,w]:g[a])if(!w&&!--deg[x])t.push(x);
    }
    dis[0][0]=1;
    q.push({0,0});
    while(!q.empty()){
        auto [a,w]=q.top();
        q.pop();
        if(vis[w][a])continue;
        vis[w][a]=true;
        if(a==n-1)continue;
        dis[w+1][a]+=dis[w][a];
        dis[w+1][a]=min(dis[w+1][a],500000001);
        if(w+1<m&&!vis[w+1][a])q.push({a,w+1});
        for(auto x:g[a]){
            if(w+x.w<m){
                dis[w+x.w][x.a]+=dis[w][a];
                dis[w+x.w][x.a]=min(dis[w+x.w][x.a],500000001);
                if(!vis[w+x.w][x.a])q.push({x.a,w+x.w});
            }
        }
    }
    for(i=0;i<m;i++)printf("%d ",dis[i][n-1]);
    return 0;
}

Compilation message (stderr)

journey.cpp: In function 'int main()':
journey.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d %d %d",&n,&m,&h);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
journey.cpp:28:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |             scanf("%d %d",&a,&w);
      |             ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 23 / 23
• Subtask 3: 26 / 26
• Subtask 4: 0 / 31