oj.uz

Submission #935026

# Submission time Handle Problem Language Result Execution time Memory
935026 2024-02-28T12:08:39 Z Hanksburger Toll (BOI17_toll) C++17
8 / 100
 427 ms 123636 KB 
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > adj[50005], rev[50005];
map<pair<int, int>, int> mp;
int dist[50005];
void recur(int l, int r, int c)
{
    int mid=(l+r)/2;
    for (int i=c*mid; i<c*(mid+1); i++)
    {
        for (int j=c*l; j<c*(r+1); j++)
            dist[j]=1e9;
        dist[i]=0;
        for (int j=c*mid-1; j>=c*l; j--)
        {
            for (int k=0; k<adj[j].size(); k++)
                dist[j]=min(dist[j], dist[adj[j][k].first]+adj[j][k].second);
            mp[{j, i}]=dist[j];
        }
        for (int j=c*(mid+1); j<c*(r+1); j++)
        {
            for (int k=0; k<rev[j].size(); k++)
                dist[j]=min(dist[j], dist[rev[j][k].first]+rev[j][k].second);
            mp[{i, j}]=dist[j];
        }
    }
    if (l+2<=mid)
        recur(l, mid-1, c);
    if (mid+2<=r)
        recur(mid+1, r, c);
}
int dfs(int l, int r, int u, int v)
{
    int mid=(l+r)/2;
    if (v<mid)
        return dfs(l, mid-1, u, v);
    if (u>mid)
        return dfs(mid+1, r, u, v);
    return mid;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int c, n, m, q;
    cin >> c >> n >> m >> q;
    for (int i=0; i<m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        rev[v].push_back({u, w});
    }
    recur(0, (n-1)/c, c);
    for (int i=0; i<q; i++)
    {
        int u, v;
        cin >> u >> v;
        int x=dfs(0, (n-1)/c, u/c, v/c);
        if (u/c==x && v/c==x)
            cout << -1 << '\n';
        else if (u/c==x || v/c==x)
            cout << mp[{u, v}] << '\n';
        else
        {
            int ans=1e9;
            for (int j=c*x; j<c*(x+1); j++)
                ans=min(ans, mp[{u, j}]+mp[{j, v}]);
            cout << (ans==1e9?-1:ans) << '\n';
        }
    }
}

Compilation message

toll.cpp: In function 'void recur(int, int, int)':
toll.cpp:16:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |             for (int k=0; k<adj[j].size(); k++)
      |                           ~^~~~~~~~~~~~~~
toll.cpp:22:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |             for (int k=0; k<rev[j].size(); k++)
      |                           ~^~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 49968 KB Output is correct
2 Incorrect 1 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 87372 KB Output is correct
2 Incorrect 2 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 3 ms 3676 KB Output is correct
8 Correct 6 ms 4700 KB Output is correct
9 Correct 5 ms 4440 KB Output is correct
10 Correct 139 ms 49540 KB Output is correct
11 Correct 265 ms 87092 KB Output is correct
12 Correct 370 ms 123156 KB Output is correct
13 Correct 413 ms 123636 KB Output is correct
14 Correct 427 ms 122164 KB Output is correct
15 Correct 350 ms 106620 KB Output is correct
16 Correct 312 ms 106836 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 3 ms 3676 KB Output is correct
8 Correct 6 ms 4700 KB Output is correct
9 Correct 5 ms 4440 KB Output is correct
10 Correct 139 ms 49540 KB Output is correct
11 Correct 265 ms 87092 KB Output is correct
12 Correct 370 ms 123156 KB Output is correct
13 Correct 413 ms 123636 KB Output is correct
14 Correct 427 ms 122164 KB Output is correct
15 Correct 350 ms 106620 KB Output is correct
16 Correct 312 ms 106836 KB Output is correct
17 Correct 288 ms 87052 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Incorrect 1 ms 2652 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 49968 KB Output is correct
2 Incorrect 1 ms 2648 KB Output isn't correct
3 Halted 0 ms 0 KB -