oj.uz

Submission #244654

# Submission time Handle Problem Language Result Execution time Memory
244654 2020-07-04T13:38:35 Z kimbj0709 Toll (BOI17_toll) C++14
8 / 100
 3000 ms 5364 KB 
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define maxn 50050
#define f first
#define s second
vector<vector<pair<int,int> > > adj(maxn);
vector<int> top;
vector<int> visited(maxn,0);
void topsort(int node){
    visited[node] = 1;
    for(auto k:adj[node]){
        if(visited[k.f]==1){
            continue;
        }
        topsort(k.f);
    }
    top.push_back(node);
}
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int k,no_of_vertex,no_of_edge,no_of_query;
    int input1,input2,input3;
    cin >> k >> no_of_vertex >> no_of_edge >> no_of_query;
    for(int i=0;i<no_of_edge;i++){
        cin >> input1 >> input2 >> input3;
        adj[input1].push_back({input2,input3});
    }
    for(int i=0;i<no_of_vertex;i++){
        if(visited[i]==0){
            topsort(i);
        }
    }
    reverse(top.begin(),top.end());
    vector<int> dist(maxn,INT_MAX);
    /*for(auto kk:top){
        cout << kk << " ";
    }
    cout << "--\n";*/
    for(int i=0;i<no_of_query;i++){
        cin >> input1 >> input2;
        for(int j=0;j<dist.size();j++){
            dist[j] = INT_MAX;
        }
        int pos = -1;
        for(int j=0;j<top.size();j++){
            if(top[j]==input1){
                pos = j;
                break;
            }
        }
        dist[input1] = 0;
        for(int j=pos;j<top.size();j++){
            if(dist[top[j]]==INT_MAX){
                continue;
            }
            for(auto kk:adj[top[j]]){
                if(dist[kk.first]>dist[top[j]]+kk.second){
                    dist[kk.first] = dist[top[j]]+kk.second;
                }
            }
        }

        if(dist[input2]==INT_MAX){
            cout << -1 << "\n";
        }
        else{
            cout << dist[input2] << "\n";
        }
    }


}

Compilation message

toll.cpp: In function 'int32_t main()':
toll.cpp:43:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<dist.size();j++){
                     ~^~~~~~~~~~~~
toll.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<top.size();j++){
                     ~^~~~~~~~~~~
toll.cpp:54:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=pos;j<top.size();j++){
                       ~^~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3085 ms 5132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3096 ms 4192 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1920 KB Output is correct
2 Correct 6 ms 1920 KB Output is correct
3 Correct 6 ms 1920 KB Output is correct
4 Correct 7 ms 1920 KB Output is correct
5 Correct 6 ms 1920 KB Output is correct
6 Correct 7 ms 1920 KB Output is correct
7 Correct 9 ms 1920 KB Output is correct
8 Correct 11 ms 2048 KB Output is correct
9 Correct 9 ms 1920 KB Output is correct
10 Correct 50 ms 3896 KB Output is correct
11 Correct 256 ms 4344 KB Output is correct
12 Correct 177 ms 5236 KB Output is correct
13 Correct 175 ms 5364 KB Output is correct
14 Correct 165 ms 4728 KB Output is correct
15 Correct 171 ms 3576 KB Output is correct
16 Correct 111 ms 3584 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1920 KB Output is correct
2 Correct 6 ms 1920 KB Output is correct
3 Correct 6 ms 1920 KB Output is correct
4 Correct 7 ms 1920 KB Output is correct
5 Correct 6 ms 1920 KB Output is correct
6 Correct 7 ms 1920 KB Output is correct
7 Correct 9 ms 1920 KB Output is correct
8 Correct 11 ms 2048 KB Output is correct
9 Correct 9 ms 1920 KB Output is correct
10 Correct 50 ms 3896 KB Output is correct
11 Correct 256 ms 4344 KB Output is correct
12 Correct 177 ms 5236 KB Output is correct
13 Correct 175 ms 5364 KB Output is correct
14 Correct 165 ms 4728 KB Output is correct
15 Correct 171 ms 3576 KB Output is correct
16 Correct 111 ms 3584 KB Output is correct
17 Execution timed out 3064 ms 4472 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3085 ms 5132 KB Time limit exceeded
2 Halted 0 ms 0 KB -