oj.uz

Submission #586406

# Submission time Handle Problem Language Result Execution time Memory
586406 2022-06-30T08:29:45 Z krit3379 Journey (NOI18_journey) C++17
69 / 100
 2000 ms 35516 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 0 ms 596 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 26 ms 1244 KB Output is correct
6 Correct 25 ms 1188 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 596 KB Output is correct
5 Correct 26 ms 1244 KB Output is correct
6 Correct 25 ms 1188 KB Output is correct
7 Correct 143 ms 5184 KB Output is correct
8 Correct 48 ms 5452 KB Output is correct
9 Correct 385 ms 7200 KB Output is correct
10 Execution timed out 2036 ms 35516 KB Time limit exceeded
11 Halted 0 ms 0 KB -