QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#784588#9802. Light Up the Griducup-team3519#WA 25ms9796kbC++171.8kb2024-11-26 15:24:462024-11-26 15:24:47

Judging History

你现在查看的是最新测评结果

  • [2024-11-26 15:24:47]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:9796kb
  • [2024-11-26 15:24:46]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define V vector
#define pb push_back
#define fi first
#define se second
#define all0(x) (x).begin(), (x).end()
#define all1(x) (x).begin() + 1, (x).end()

typedef long long LL;
typedef pair<int, int> pi;

const int INF = 2e9 + 1000;

void solve() {
    int q; cin >> q;
    V<int> c(5);        
    for(int i = 1; i <= 4; i++) cin >> c[i];
    V<int> dis(1 << 4, -1);
    priority_queue<pi, V<pi>, greater<pi>> pque;
    pque.push({0, 0});
    V<pi> chg;
    chg.pb({1, c[1]});
    chg.pb({2, c[1]});
    chg.pb({4, c[1]});
    chg.pb({8, c[1]});
    chg.pb({3, c[2]});
    chg.pb({12, c[2]});
    chg.pb({5, c[3]});
    chg.pb({10, c[3]});
    chg.pb({15, c[4]});

    while(pque.size()) {
        auto [d, x] = pque.top();
        pque.pop();
        if(dis[x] != -1) continue;
        dis[x] = d;
        for(auto [v, cost] : chg) {
            int y = v ^ x;
            pque.push({cost + d, y});
        }
    }

    V<V<int>> dp(1 << 16, V<int>(1 << 4, INF / 2));
    dp[0][0] = 0;
    for(int i = 0; i < (1 << 16); i++) {
        for(int j = 0; j < 1 << 4; j++) {
            for(int k = 0; k < 16; k++) {
                if(!(i >> k & 1)) {
                    dp[i + (1 << k)][k] = min(dp[i + (1 << k)][k], dp[i][j] + dis[j ^ k]);
                }
            }
        }
    }
    
    for(int i = 1; i <= q; i++) {
        int m; cin >> m;
        int need = 0;
        for(int i = 1; i <= m; i++) {
            string s; cin >> s;
            string t; cin >> t;
            int tmp = (s[0] - '0') + (s[1] - '0') * 2 + (t[0] - '0') * 4 + (t[1] - '0') * 8;
            need |= 1 << tmp;
        }
        cout << *min_element(all0(dp[need])) + 1 << "\n";
        
    }

}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
}

詳細信息

Test #1:

score: 100
Accepted
time: 24ms
memory: 9668kb

input:

2 1000 100 10 1
4
10
00

01
00

00
10

00
01
1
11
11

output:

1121
2

result:

ok 2 number(s): "1121 2"

Test #2:

score: 0
Accepted
time: 25ms
memory: 9672kb

input:

2 1 1 1 1
4
10
00

01
00

00
10

00
01
1
11
11

output:

5
2

result:

ok 2 number(s): "5 2"

Test #3:

score: -100
Wrong Answer
time: 24ms
memory: 9796kb

input:

1 1000000 1000000 1000000 1000000
1
11
11

output:

1000001

result:

wrong answer 1st numbers differ - expected: '2000000', found: '1000001'