oj.uz

답안 #935026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -