oj.uz

Submission #787072

# Submission time Handle Problem Language Result Execution time Memory
787072 2023-07-18T18:39:42 Z Ozy Voting Cities (NOI22_votingcity) C++17
45 / 100
 1000 ms 8356 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 5000
//para la cola
#define v first
#define pos second.first
#define usados second.second
//para los hijos
#define des first
#define w second

lli n,k,m,a,b,c,res,q,s;
lli votantes[MAX+2],dp[MAX+2][(1<<5)],costos[5];
vector<pll> hijos[MAX+2];
priority_queue<pair<lli,pll> > cola;
pair<lli,pll> act;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> k;
    rep(i,1,k) {
        cin >> a;
        votantes[a] = 1;
    }
    rep(i,1,m) {
        cin >> a >> b >> c;
        hijos[a].push_back({b,c});
    }

    cin >> q;
    rep(Q,1,q) {

        //limpia
        rep(i,0,n-1) {
            rep(j,0,(1<<5)-1) {
                dp[i][j] = 0;
            }
        }
        while (!cola.empty()) cola.pop();

        cin >> s;
        rep(i,0,4) cin >> costos[i];

        res = 0;
        cola.push({-1,{s,0}});
        while (!cola.empty()) {

            act = cola.top();
            cola.pop();
            act.v *= -1;

            if (dp[act.pos][act.usados] != 0) continue;
            dp[act.pos][act.usados] = act.v;

            if (votantes[act.pos] == 1) {
                res = act.v;
                break;
            }

            //busaco usando alguno de mis hijos
            rep(pot,0,4) {
                if (act.usados & (1<<pot) || costos[pot] == -1) continue;
                for(auto h : hijos[act.pos]) {
                    if (dp[h.des][act.usados+(1<<pot)] != 0) continue;
                    a = h.w/10;
                    a *= 9 - pot;
                    a += costos[pot];
                    cola.push({-(act.v + a),{h.des,act.usados+(1<<pot)}});
                }
            }
            for(auto h : hijos[act.pos]) {
                if (dp[h.des][act.usados] != 0) continue;
                cola.push({-(act.v + h.w),{h.des,act.usados}});
            }

        }

        res--;
        cout << res << "\n";
    }

    //restar uno siempre a res ya que se lo sumo al principio

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2132 KB Output is correct
2 Correct 3 ms 1876 KB Output is correct
3 Correct 5 ms 2116 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2132 KB Output is correct
2 Correct 3 ms 1876 KB Output is correct
3 Correct 5 ms 2116 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 20 ms 2188 KB Output is correct
7 Correct 17 ms 1836 KB Output is correct
8 Correct 49 ms 2204 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2132 KB Output is correct
2 Correct 3 ms 1876 KB Output is correct
3 Correct 5 ms 2116 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 20 ms 2188 KB Output is correct
7 Correct 17 ms 1836 KB Output is correct
8 Correct 49 ms 2204 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 6 ms 2092 KB Output is correct
12 Correct 8 ms 1876 KB Output is correct
13 Correct 10 ms 2132 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2132 KB Output is correct
2 Correct 3 ms 1876 KB Output is correct
3 Correct 5 ms 2116 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 116 ms 8324 KB Output is correct
7 Correct 6 ms 1876 KB Output is correct
8 Correct 11 ms 3792 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2132 KB Output is correct
2 Correct 3 ms 1876 KB Output is correct
3 Correct 5 ms 2116 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 20 ms 2188 KB Output is correct
7 Correct 17 ms 1836 KB Output is correct
8 Correct 49 ms 2204 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 116 ms 8324 KB Output is correct
12 Correct 6 ms 1876 KB Output is correct
13 Correct 11 ms 3792 KB Output is correct
14 Execution timed out 1072 ms 8356 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2120 KB Output is correct
2 Correct 6 ms 2188 KB Output is correct
3 Correct 5 ms 1876 KB Output is correct
4 Correct 35 ms 2344 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 712 KB Output is correct
2 Correct 7 ms 580 KB Output is correct
3 Correct 5 ms 468 KB Output is correct
4 Correct 5 ms 596 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct

Subtask #8
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2132 KB Output is correct
2 Correct 3 ms 1876 KB Output is correct
3 Correct 5 ms 2116 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 20 ms 2188 KB Output is correct
7 Correct 17 ms 1836 KB Output is correct
8 Correct 49 ms 2204 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 6 ms 2092 KB Output is correct
12 Correct 8 ms 1876 KB Output is correct
13 Correct 10 ms 2132 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 116 ms 8324 KB Output is correct
17 Correct 6 ms 1876 KB Output is correct
18 Correct 11 ms 3792 KB Output is correct
19 Execution timed out 1072 ms 8356 KB Time limit exceeded
20 Halted 0 ms 0 KB -