oj.uz

Submission #584241

# Submission time Handle Problem Language Result Execution time Memory
584241 2022-06-27T05:16:46 Z 반딧불(#8375) Wild Boar (JOI18_wild_boar) C++17
12 / 100
 10 ms 3316 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge{
    int s, e, i; ll v;
    Edge(){}
    Edge(int s, int e, int i, ll v): s(s), e(e), i(i), v(v){}
};

struct dat{
    int x; ll y;
    dat(){}
    dat(int x, ll y): x(x), y(y){}
    bool operator<(const dat &r)const{
        return y>r.y;
    }
};

int n, m, k, l;
vector<int> link[2002];
Edge edge[4002];
int arr[2002];
ll dist[4002][4002];

void init(){
    for(int i=0; i<m*2; i++){
        for(int j=0; j<m*2; j++) dist[i][j] = 1e18;
        priority_queue<dat> pq;
        pq.push(dat(i, 0));
        while(!pq.empty()){
            dat tmp = pq.top(); pq.pop();
            if(dist[i][tmp.x] < 1e18) continue;
            int xe = tmp.x, x = edge[xe].e;
            dist[i][xe] = tmp.y;
            for(auto ye: link[x]){
                if((xe^ye) == 1) continue;
                pq.push(dat(ye, tmp.y + edge[ye].v));
            }
        }
    }
}

ll DP[2][4002];
void solve(){
    for(int i=0; i<m*2; i++) DP[0][i] = DP[1][i] = 1e18;
    for(int i=0; i<m*2; i++){
        if(edge[i].s != arr[1]) continue;
        DP[1][edge[i].i] = edge[i].v;
    }
    for(int d=2; d<=l; d++){
        int b = d%2;
        for(int i=0; i<m*2; i++) DP[b][i] = 1e18;
        for(int i=0; i<m*2; i++){
            for(int j=0; j<m*2; j++){
                if(edge[j].e != arr[d]) continue;
                DP[b][j] = min(DP[b][j], DP[!b][i] + dist[i][j]);
            }
        }
    }
    ll ans = 1e18;
    for(int i=0; i<m*2; i++) if(edge[i].e == arr[l]) ans = min(ans, DP[l%2][i]);
    printf("%lld\n", ans == 1e18 ? -1 : ans);
}

int main(){
    scanf("%d %d %d %d", &n, &m, &k, &l);
    for(int i=0; i<m; i++){
        scanf("%d %d %lld", &edge[i*2].s, &edge[i*2].e, &edge[i*2].v);
        edge[i*2+1] = edge[i*2];
        swap(edge[i*2+1].s, edge[i*2+1].e);
        edge[i*2].i = i*2, edge[i*2+1].i = i*2+1;

        link[edge[i*2].s].push_back(i*2);
        link[edge[i*2+1].s].push_back(i*2+1);
    }
    init();

    for(int i=1; i<=l; i++) scanf("%d", &arr[i]);
    for(int i=1; i<=k; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        arr[x] = y;
        solve();
    }
}

Compilation message

wild_boar.cpp: In function 'int main()':
wild_boar.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d %d %d %d", &n, &m, &k, &l);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf("%d %d %lld", &edge[i*2].s, &edge[i*2].e, &edge[i*2].v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:81:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     for(int i=1; i<=l; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
wild_boar.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 356 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 360 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 356 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 356 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 360 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 356 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 4 ms 740 KB Output is correct
27 Runtime error 10 ms 3316 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 0 ms 340 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 356 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 360 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 356 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 4 ms 740 KB Output is correct
27 Runtime error 10 ms 3316 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 0 ms 340 KB Output is correct
2 Correct 1 ms 360 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 356 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 360 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 356 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 4 ms 740 KB Output is correct
27 Runtime error 10 ms 3316 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -