oj.uz

답안 #518904

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
518904 2022-01-25T04:58:06 Z azberjibiou Commuter Pass (JOI18_commuter_pass) C++17
100 / 100
 358 ms 34608 KB 
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fir first
#define sec second
#define pdd pair<double, double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pmax pair<__int128, __int128>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=100020;
const int mxM=2500000;
const int mxK=105;
const int MOD=1000000007;
const ll INF=1000000000000000001;
int N, M, S, T, U, V;
vector <pll> v[mxN];
ll dis[4][mxN];
priority_queue <pll> pq;
bool Chk[mxN];
vector <int> rv[2][mxN];
int rdeg[mxN];
queue <int> que;
ll sub[2][mxN];
ll ans=INF;
void dijkstra(int st, int idx)
{
    while(!pq.empty())  pq.pop();
    for(int i=1;i<=N;i++)   Chk[i]=false;
    for(int i=1;i<=N;i++)   dis[idx][i]=INF;
    dis[idx][st]=0;
    pq.push({0, st});
    while(!pq.empty())
    {
        int now=pq.top().sec;
        pq.pop();
        if(Chk[now])    continue;
        Chk[now]=true;
        for(pll nxt : v[now])
        {
            if(dis[idx][nxt.fir]>dis[idx][now]+nxt.sec)
            {
                dis[idx][nxt.fir]=dis[idx][now]+nxt.sec;
                pq.push({-dis[idx][nxt.fir], nxt.fir});
            }
        }
    }
}
void dfs0(int now)
{
    Chk[now]=true;
    for(pll nxt : v[now])   if(dis[0][now]+dis[1][nxt.fir]+nxt.sec==dis[0][T])
    {
        rv[0][now].push_back(nxt.fir);
        rv[1][nxt.fir].push_back(now);
        rdeg[now]++;
        if(!Chk[nxt.fir])   dfs0(nxt.fir);
    }
}
void dfs1(int now)
{
    Chk[now]=true;
    sub[0][now]=dis[3][now];
    sub[1][now]=dis[2][now];
    for(int nxt : rv[0][now])
    {
        if(!Chk[nxt])   dfs1(nxt);
        sub[0][now]=min(sub[0][now], sub[0][nxt]);
        sub[1][now]=min(sub[1][now], sub[1][nxt]);
    }
}
int main()
{
    gibon
    cin >> N >> M >> S >> T >> U >> V;
    for(int i=0;i<M;i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].emplace_back(b, c);
        v[b].emplace_back(a, c);
    }
    dijkstra(S, 0);
    dijkstra(T, 1);
    dijkstra(U, 2);
    dijkstra(V, 3);
    /*for(int i=0;i<4;i++)
    {
        for(int j=1;j<=N;j++)
        {
            printf("dis[%d][%d]=%lld\n", i, j, dis[i][j]);
        }
    }*/
    for(int i=1;i<=N;i++)   Chk[i]=false;
    dfs0(S);
    for(int i=1;i<=N;i++)   if(Chk[i] && !rdeg[i])  que.push(i);
    while(!que.empty())
    {
        int now=que.front();
        que.pop();
        if(now==T)  continue;
        Chk[now]=false;
        for(int nxt : rv[1][now])
        {
            rdeg[nxt]--;
            if(!rdeg[nxt])  que.push(nxt);
        }
    }
    vector <int> tmp;
    for(int i=1;i<=N;i++)
    {
        if(!Chk[i])
        {
            rv[0][i].clear();   rv[1][i].clear();
            continue;
        }
        tmp.clear();
        for(int ele : rv[0][i]) if(Chk[ele])    tmp.push_back(ele);
        swap(tmp, rv[0][i]);
        tmp.clear();
        for(int ele : rv[1][i]) if(Chk[ele])    tmp.push_back(ele);
        swap(tmp, rv[1][i]);
    }
    for(int i=1;i<=N;i++)   Chk[i]=false;
    dfs1(S);
    for(int i=1;i<=N;i++)   if(Chk[i])
    {
        ans=min(ans, dis[2][i]+sub[0][i]);
        ans=min(ans, dis[3][i]+sub[1][i]);
    }
    ans=min(ans, dis[2][V]);
    cout << ans;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 257 ms 22300 KB Output is correct
2 Correct 285 ms 25172 KB Output is correct
3 Correct 317 ms 34608 KB Output is correct
4 Correct 268 ms 23264 KB Output is correct
5 Correct 290 ms 26468 KB Output is correct
6 Correct 285 ms 22584 KB Output is correct
7 Correct 307 ms 27304 KB Output is correct
8 Correct 326 ms 30416 KB Output is correct
9 Correct 257 ms 26352 KB Output is correct
10 Correct 221 ms 26216 KB Output is correct
11 Correct 142 ms 26696 KB Output is correct
12 Correct 283 ms 26268 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 294 ms 28000 KB Output is correct
2 Correct 298 ms 28512 KB Output is correct
3 Correct 297 ms 27680 KB Output is correct
4 Correct 298 ms 28284 KB Output is correct
5 Correct 302 ms 29524 KB Output is correct
6 Correct 297 ms 33464 KB Output is correct
7 Correct 325 ms 34496 KB Output is correct
8 Correct 294 ms 28476 KB Output is correct
9 Correct 297 ms 29444 KB Output is correct
10 Correct 304 ms 27756 KB Output is correct
11 Correct 143 ms 28228 KB Output is correct
12 Correct 317 ms 34104 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 8780 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 16 ms 10844 KB Output is correct
5 Correct 10 ms 9028 KB Output is correct
6 Correct 4 ms 7504 KB Output is correct
7 Correct 5 ms 7528 KB Output is correct
8 Correct 5 ms 7588 KB Output is correct
9 Correct 5 ms 7432 KB Output is correct
10 Correct 10 ms 9044 KB Output is correct
11 Correct 4 ms 7372 KB Output is correct
12 Correct 4 ms 7392 KB Output is correct
13 Correct 4 ms 7372 KB Output is correct
14 Correct 4 ms 7492 KB Output is correct
15 Correct 4 ms 7372 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 257 ms 22300 KB Output is correct
2 Correct 285 ms 25172 KB Output is correct
3 Correct 317 ms 34608 KB Output is correct
4 Correct 268 ms 23264 KB Output is correct
5 Correct 290 ms 26468 KB Output is correct
6 Correct 285 ms 22584 KB Output is correct
7 Correct 307 ms 27304 KB Output is correct
8 Correct 326 ms 30416 KB Output is correct
9 Correct 257 ms 26352 KB Output is correct
10 Correct 221 ms 26216 KB Output is correct
11 Correct 142 ms 26696 KB Output is correct
12 Correct 283 ms 26268 KB Output is correct
13 Correct 294 ms 28000 KB Output is correct
14 Correct 298 ms 28512 KB Output is correct
15 Correct 297 ms 27680 KB Output is correct
16 Correct 298 ms 28284 KB Output is correct
17 Correct 302 ms 29524 KB Output is correct
18 Correct 297 ms 33464 KB Output is correct
19 Correct 325 ms 34496 KB Output is correct
20 Correct 294 ms 28476 KB Output is correct
21 Correct 297 ms 29444 KB Output is correct
22 Correct 304 ms 27756 KB Output is correct
23 Correct 143 ms 28228 KB Output is correct
24 Correct 317 ms 34104 KB Output is correct
25 Correct 11 ms 8780 KB Output is correct
26 Correct 4 ms 7372 KB Output is correct
27 Correct 4 ms 7372 KB Output is correct
28 Correct 16 ms 10844 KB Output is correct
29 Correct 10 ms 9028 KB Output is correct
30 Correct 4 ms 7504 KB Output is correct
31 Correct 5 ms 7528 KB Output is correct
32 Correct 5 ms 7588 KB Output is correct
33 Correct 5 ms 7432 KB Output is correct
34 Correct 10 ms 9044 KB Output is correct
35 Correct 4 ms 7372 KB Output is correct
36 Correct 4 ms 7392 KB Output is correct
37 Correct 4 ms 7372 KB Output is correct
38 Correct 4 ms 7492 KB Output is correct
39 Correct 4 ms 7372 KB Output is correct
40 Correct 280 ms 26092 KB Output is correct
41 Correct 257 ms 26300 KB Output is correct
42 Correct 259 ms 26432 KB Output is correct
43 Correct 176 ms 31244 KB Output is correct
44 Correct 167 ms 31256 KB Output is correct
45 Correct 336 ms 32744 KB Output is correct
46 Correct 358 ms 32736 KB Output is correct
47 Correct 276 ms 27072 KB Output is correct
48 Correct 185 ms 27240 KB Output is correct
49 Correct 206 ms 25704 KB Output is correct
50 Correct 325 ms 31392 KB Output is correct
51 Correct 325 ms 32792 KB Output is correct