oj.uz

Submission #854713

# Submission time Handle Problem Language Result Execution time Memory
854713 2023-09-28T15:30:56 Z khanhtai Wild Boar (JOI18_wild_boar) C++17
12 / 100
 123 ms 984916 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 = 501;
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 123 ms 984624 KB Output is correct
2 Correct 105 ms 984588 KB Output is correct
3 Correct 107 ms 984788 KB Output is correct
4 Correct 106 ms 984652 KB Output is correct
5 Correct 108 ms 984916 KB Output is correct
6 Correct 107 ms 984772 KB Output is correct
7 Correct 106 ms 984772 KB Output is correct
8 Correct 106 ms 984656 KB Output is correct
9 Correct 105 ms 984652 KB Output is correct
10 Correct 108 ms 984660 KB Output is correct
11 Correct 108 ms 984660 KB Output is correct
12 Correct 104 ms 984656 KB Output is correct
13 Correct 105 ms 984828 KB Output is correct
14 Correct 112 ms 984792 KB Output is correct
15 Correct 107 ms 984660 KB Output is correct
16 Correct 104 ms 984656 KB Output is correct
17 Correct 106 ms 984588 KB Output is correct
18 Correct 104 ms 984620 KB Output is correct
19 Correct 105 ms 984660 KB Output is correct
20 Correct 105 ms 984656 KB Output is correct
21 Correct 110 ms 984656 KB Output is correct
22 Correct 111 ms 984652 KB Output is correct
23 Correct 105 ms 984656 KB Output is correct
24 Correct 106 ms 984644 KB Output is correct
25 Correct 108 ms 984760 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 984624 KB Output is correct
2 Correct 105 ms 984588 KB Output is correct
3 Correct 107 ms 984788 KB Output is correct
4 Correct 106 ms 984652 KB Output is correct
5 Correct 108 ms 984916 KB Output is correct
6 Correct 107 ms 984772 KB Output is correct
7 Correct 106 ms 984772 KB Output is correct
8 Correct 106 ms 984656 KB Output is correct
9 Correct 105 ms 984652 KB Output is correct
10 Correct 108 ms 984660 KB Output is correct
11 Correct 108 ms 984660 KB Output is correct
12 Correct 104 ms 984656 KB Output is correct
13 Correct 105 ms 984828 KB Output is correct
14 Correct 112 ms 984792 KB Output is correct
15 Correct 107 ms 984660 KB Output is correct
16 Correct 104 ms 984656 KB Output is correct
17 Correct 106 ms 984588 KB Output is correct
18 Correct 104 ms 984620 KB Output is correct
19 Correct 105 ms 984660 KB Output is correct
20 Correct 105 ms 984656 KB Output is correct
21 Correct 110 ms 984656 KB Output is correct
22 Correct 111 ms 984652 KB Output is correct
23 Correct 105 ms 984656 KB Output is correct
24 Correct 106 ms 984644 KB Output is correct
25 Correct 108 ms 984760 KB Output is correct
26 Correct 105 ms 984768 KB Output is correct
27 Runtime error 22 ms 344 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 123 ms 984624 KB Output is correct
2 Correct 105 ms 984588 KB Output is correct
3 Correct 107 ms 984788 KB Output is correct
4 Correct 106 ms 984652 KB Output is correct
5 Correct 108 ms 984916 KB Output is correct
6 Correct 107 ms 984772 KB Output is correct
7 Correct 106 ms 984772 KB Output is correct
8 Correct 106 ms 984656 KB Output is correct
9 Correct 105 ms 984652 KB Output is correct
10 Correct 108 ms 984660 KB Output is correct
11 Correct 108 ms 984660 KB Output is correct
12 Correct 104 ms 984656 KB Output is correct
13 Correct 105 ms 984828 KB Output is correct
14 Correct 112 ms 984792 KB Output is correct
15 Correct 107 ms 984660 KB Output is correct
16 Correct 104 ms 984656 KB Output is correct
17 Correct 106 ms 984588 KB Output is correct
18 Correct 104 ms 984620 KB Output is correct
19 Correct 105 ms 984660 KB Output is correct
20 Correct 105 ms 984656 KB Output is correct
21 Correct 110 ms 984656 KB Output is correct
22 Correct 111 ms 984652 KB Output is correct
23 Correct 105 ms 984656 KB Output is correct
24 Correct 106 ms 984644 KB Output is correct
25 Correct 108 ms 984760 KB Output is correct
26 Correct 105 ms 984768 KB Output is correct
27 Runtime error 22 ms 344 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 123 ms 984624 KB Output is correct
2 Correct 105 ms 984588 KB Output is correct
3 Correct 107 ms 984788 KB Output is correct
4 Correct 106 ms 984652 KB Output is correct
5 Correct 108 ms 984916 KB Output is correct
6 Correct 107 ms 984772 KB Output is correct
7 Correct 106 ms 984772 KB Output is correct
8 Correct 106 ms 984656 KB Output is correct
9 Correct 105 ms 984652 KB Output is correct
10 Correct 108 ms 984660 KB Output is correct
11 Correct 108 ms 984660 KB Output is correct
12 Correct 104 ms 984656 KB Output is correct
13 Correct 105 ms 984828 KB Output is correct
14 Correct 112 ms 984792 KB Output is correct
15 Correct 107 ms 984660 KB Output is correct
16 Correct 104 ms 984656 KB Output is correct
17 Correct 106 ms 984588 KB Output is correct
18 Correct 104 ms 984620 KB Output is correct
19 Correct 105 ms 984660 KB Output is correct
20 Correct 105 ms 984656 KB Output is correct
21 Correct 110 ms 984656 KB Output is correct
22 Correct 111 ms 984652 KB Output is correct
23 Correct 105 ms 984656 KB Output is correct
24 Correct 106 ms 984644 KB Output is correct
25 Correct 108 ms 984760 KB Output is correct
26 Correct 105 ms 984768 KB Output is correct
27 Runtime error 22 ms 344 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -