oj.uz

Submission #854715

# Submission time Handle Problem Language Result Execution time Memory
854715 2023-09-28T15:32:17 Z khanhtai Wild Boar (JOI18_wild_boar) C++14
12 / 100
 221 ms 996684 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "wildboar"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 503;
vector<iii> g[MAXN];
int plan[MAXN];
int n,m,q,l,u,v,w,dist[MAXN][MAXN][MAXN];
bool spec[MAXN];
void dijkstra(){
    memset(dist,0x3f,sizeof(dist));
    dist[plan[1]][1][0] = 0;
    priority_queue<array<int,4>,vector<array<int,4>>,greater<array<int,4>>> pq;
    pq.push({0,plan[1],1,0});
    while(!pq.empty()){
        array<int,4> tp = pq.top();
        int du = tp[0];
        int u = tp[1];
        int cur = tp[2];
        int cur_edge_id = tp[3];
        pq.pop();
        if (du > dist[u][cur][cur_edge_id]) continue;
        for(auto pt: g[u]){
            int v = pt.se.fi;
            int idedge = pt.fi;
            int w = pt.se.se;
            if (cur_edge_id == idedge) continue;
            if (v == plan[cur+1] and dist[v][cur+1][idedge] > dist[u][cur][cur_edge_id] + w){
                dist[v][cur+1][idedge] = dist[u][cur][cur_edge_id] + w;
                pq.push({dist[v][cur+1][idedge],v,cur+1,idedge});
            }
            if (v != plan[cur+1] and dist[v][cur][idedge] > dist[u][cur][cur_edge_id] + w){
                dist[v][cur][idedge] = dist[u][cur][cur_edge_id] + w;
                pq.push({dist[v][cur][idedge],v,cur,idedge});
            }
        }
    }
    int ans = INF;
    for(int i=1;i<=m;i++){
        ans = min(ans, dist[plan[l]][l][i]);
    }
    if (ans == INF) cout<<-1<<endl;
    else cout<<ans<<endl;
}
main()
{
    fast;
//    freopen(TASKNAME".inp","r",stdin);
//    freopen(TASKNAME".out","w",stdout);
    cin>>n>>m>>q>>l;
    memset(spec,false,sizeof(spec));
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        g[u].pb({i,{v,w}});
        g[v].pb({i,{u,w}});
    }

    for(int i=1;i<=l;i++){
        cin>>plan[i];
        spec[plan[i]] = true;
    }
    for(int i=1;i<=q;i++){
        int p,k;
        cin>>p>>k;
        spec[plan[p]] = false;
        plan[p] = k;
        spec[plan[p]] = true;
        dijkstra();

    }



}

Compilation message

wild_boar.cpp:61:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   61 | main()
      | ^~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 996488 KB Output is correct
2 Correct 140 ms 996432 KB Output is correct
3 Correct 221 ms 996436 KB Output is correct
4 Correct 216 ms 996432 KB Output is correct
5 Correct 168 ms 996520 KB Output is correct
6 Correct 147 ms 996548 KB Output is correct
7 Correct 138 ms 996672 KB Output is correct
8 Correct 128 ms 996432 KB Output is correct
9 Correct 116 ms 996544 KB Output is correct
10 Correct 108 ms 996492 KB Output is correct
11 Correct 113 ms 996684 KB Output is correct
12 Correct 108 ms 996436 KB Output is correct
13 Correct 110 ms 996544 KB Output is correct
14 Correct 111 ms 996416 KB Output is correct
15 Correct 109 ms 996480 KB Output is correct
16 Correct 105 ms 996436 KB Output is correct
17 Correct 108 ms 996616 KB Output is correct
18 Correct 113 ms 996560 KB Output is correct
19 Correct 117 ms 996472 KB Output is correct
20 Correct 107 ms 996436 KB Output is correct
21 Correct 110 ms 996532 KB Output is correct
22 Correct 107 ms 996572 KB Output is correct
23 Correct 112 ms 996540 KB Output is correct
24 Correct 108 ms 996436 KB Output is correct
25 Correct 110 ms 996532 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 996488 KB Output is correct
2 Correct 140 ms 996432 KB Output is correct
3 Correct 221 ms 996436 KB Output is correct
4 Correct 216 ms 996432 KB Output is correct
5 Correct 168 ms 996520 KB Output is correct
6 Correct 147 ms 996548 KB Output is correct
7 Correct 138 ms 996672 KB Output is correct
8 Correct 128 ms 996432 KB Output is correct
9 Correct 116 ms 996544 KB Output is correct
10 Correct 108 ms 996492 KB Output is correct
11 Correct 113 ms 996684 KB Output is correct
12 Correct 108 ms 996436 KB Output is correct
13 Correct 110 ms 996544 KB Output is correct
14 Correct 111 ms 996416 KB Output is correct
15 Correct 109 ms 996480 KB Output is correct
16 Correct 105 ms 996436 KB Output is correct
17 Correct 108 ms 996616 KB Output is correct
18 Correct 113 ms 996560 KB Output is correct
19 Correct 117 ms 996472 KB Output is correct
20 Correct 107 ms 996436 KB Output is correct
21 Correct 110 ms 996532 KB Output is correct
22 Correct 107 ms 996572 KB Output is correct
23 Correct 112 ms 996540 KB Output is correct
24 Correct 108 ms 996436 KB Output is correct
25 Correct 110 ms 996532 KB Output is correct
26 Correct 110 ms 996504 KB Output is correct
27 Runtime error 19 ms 348 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 996488 KB Output is correct
2 Correct 140 ms 996432 KB Output is correct
3 Correct 221 ms 996436 KB Output is correct
4 Correct 216 ms 996432 KB Output is correct
5 Correct 168 ms 996520 KB Output is correct
6 Correct 147 ms 996548 KB Output is correct
7 Correct 138 ms 996672 KB Output is correct
8 Correct 128 ms 996432 KB Output is correct
9 Correct 116 ms 996544 KB Output is correct
10 Correct 108 ms 996492 KB Output is correct
11 Correct 113 ms 996684 KB Output is correct
12 Correct 108 ms 996436 KB Output is correct
13 Correct 110 ms 996544 KB Output is correct
14 Correct 111 ms 996416 KB Output is correct
15 Correct 109 ms 996480 KB Output is correct
16 Correct 105 ms 996436 KB Output is correct
17 Correct 108 ms 996616 KB Output is correct
18 Correct 113 ms 996560 KB Output is correct
19 Correct 117 ms 996472 KB Output is correct
20 Correct 107 ms 996436 KB Output is correct
21 Correct 110 ms 996532 KB Output is correct
22 Correct 107 ms 996572 KB Output is correct
23 Correct 112 ms 996540 KB Output is correct
24 Correct 108 ms 996436 KB Output is correct
25 Correct 110 ms 996532 KB Output is correct
26 Correct 110 ms 996504 KB Output is correct
27 Runtime error 19 ms 348 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 996488 KB Output is correct
2 Correct 140 ms 996432 KB Output is correct
3 Correct 221 ms 996436 KB Output is correct
4 Correct 216 ms 996432 KB Output is correct
5 Correct 168 ms 996520 KB Output is correct
6 Correct 147 ms 996548 KB Output is correct
7 Correct 138 ms 996672 KB Output is correct
8 Correct 128 ms 996432 KB Output is correct
9 Correct 116 ms 996544 KB Output is correct
10 Correct 108 ms 996492 KB Output is correct
11 Correct 113 ms 996684 KB Output is correct
12 Correct 108 ms 996436 KB Output is correct
13 Correct 110 ms 996544 KB Output is correct
14 Correct 111 ms 996416 KB Output is correct
15 Correct 109 ms 996480 KB Output is correct
16 Correct 105 ms 996436 KB Output is correct
17 Correct 108 ms 996616 KB Output is correct
18 Correct 113 ms 996560 KB Output is correct
19 Correct 117 ms 996472 KB Output is correct
20 Correct 107 ms 996436 KB Output is correct
21 Correct 110 ms 996532 KB Output is correct
22 Correct 107 ms 996572 KB Output is correct
23 Correct 112 ms 996540 KB Output is correct
24 Correct 108 ms 996436 KB Output is correct
25 Correct 110 ms 996532 KB Output is correct
26 Correct 110 ms 996504 KB Output is correct
27 Runtime error 19 ms 348 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -