QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#784890#9802. Light Up the Gridxbzxzn#WA 22ms5704kbC++206.1kb2024-11-26 16:15:202024-11-26 16:15:21

Judging History

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

  • [2024-11-26 16:15:21]
  • 评测
  • 测评结果：WA
  • 用时：22ms
  • 内存：5704kb
查看
  • [2024-11-26 16:15:20]
  • 提交

answer

////#include <bits/stdc++.h>
////using namespace std;
////using i64 = long long;
////#define int long long
////const int inf=1e18;
////signed main() {
////    std::ios::sync_with_stdio(false);
////    std::cin.tie(nullptr);
////    int T;cin>>T;
////    vector<int>a(5);
////    for(int i=0;i<4;i++)cin>>a[i];
////    vector<array<int,2>>e;
////    e.push_back({a[0],1});
////    e.push_back({a[0],2});
////    e.push_back({a[0],4});
////    e.push_back({a[0],8});
////    e.push_back({a[1],3});
////    e.push_back({a[1],12});
////    e.push_back({a[2],10});
////    e.push_back({a[2],5});
////    e.push_back({a[3],15});
////    const int N=16;
////    vector<int>dis(N,inf);
////    int s=15;
////    dis[s]=0;
////    priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>q;
////
////}
//#include <bits/stdc++.h>
//
//using namespace std;
//using i64 = long long;
//#define int long long
//const int inf=1e16;
//signed main() {
//    std::ios::sync_with_stdio(false);
//    std::cin.tie(nullptr);
//
//
//    int T;
//    std::cin >> T;
//    std::vector<int> a(4);
//    std::vector<std::array<int, 2>> e;
//    for (int i = 0; i < 4; i++) {
//        std::cin >> a[i];
//    }
//    e.push_back({a[0], 1});
//    e.push_back({a[0], 2});
//    e.push_back({a[0], 4});
//    e.push_back({a[0], 8});
//    e.push_back({a[1], 3});
//    e.push_back({a[1], 12});
//    e.push_back({a[2], 10});
//    e.push_back({a[2], 5});
//    e.push_back({a[3], 15});
//    const int N = 16;
//    std::vector dis(N, std::vector<i64>(N, inf));
//    for (int i = 0; i < N; i++) {
//        dis[i][i] = 0;
//        for (auto [w, st] : e) {
//            int j = (i ^ st);
//            dis[i][j] = dis[j][i] = std::min(dis[i][j], 1LL * w);
//        }
//    }
//    for (int k = 0; k < N; k++) {
//        for (int i = 0; i < N; i++) {
//            for (int j = 0; j < N; j++) {
//                dis[i][j] = std::min(dis[i][j],dis[i][k]+dis[k][j]);
//            }
//        }
//    }
//    dis[15][15]=inf;
//    for(int i=0;i<N;i++){
//        dis[15][15]=min(dis[15][15],dis[i][15]+dis[15][i]);
//    }
//    std::vector<i64> pre(1 << N+1), dp(1 << N+1, 1E12),vis(1<<N+1);
//    dp[0] = 0;
//    std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<>> q;
//    q.emplace(0, 0);
//    while (!q.empty()) {
//        auto [val, st] = q.top();
//        q.pop();
//        if(vis[st])continue;
//        vis[st]=1;
//        for (int i = 0; i < N; i++) {
//            if (~st >> i) {
//                int ns = st | (1 << i);
//                int state=i^pre[st];
//                if(dp[ns]>dp[st]+dis[state][15]){
//                    dp[ns]=dp[st]+dis[state][15];
//                    pre[ns]=pre[st]^15^state;
//                    q.push({dp[ns],ns});
//                }
//            }
//        }
//    }
//
//    while (T--) {
//        int n;
//        std::cin >> n;
//        std::vector<int> b(n);
//        for (int i = 0; i < n; i++) {
//            std::string t;
//            std::cin >> t;
//            b[i] = ((t[0] - '0') *8);
//            b[i] += ((t[1] - '0') *4);
//            std::cin >> t;
//            b[i] += ((t[0] - '0') *2);
//            b[i] += ((t[1] - '0'));
//        }
//        int state=0;
//        for(int i=0;i<n;i++){
//            state|=(1<<b[i]);
//        }
//        std::cout<<dp[state]<<'\n';
//    }
//}
#include <bits/stdc++.h>

using i64 = long long;
#define int long long
using namespace std;
const int inf=1e18;
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T;
    std::cin >> T;
    std::vector<int> a(4);
    std::vector<std::array<int, 2>> e;
    for (int i = 0; i < 4; i++) {
        std::cin >> a[i];
    }
    e.push_back({a[0], 1});
    e.push_back({a[0], 2});
    e.push_back({a[0], 4});
    e.push_back({a[0], 8});
    e.push_back({a[1], 3});
    e.push_back({a[1], 12});
    e.push_back({a[2], 10});
    e.push_back({a[2], 5});
    e.push_back({a[3], 15});
    const int N = 16;
    std::vector<int>dis(N+1,inf);
    std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<>> q;
    vector<int>vis(1<<N);
    dis[15]=0;
    q.push({dis[15],15});
    while(!q.empty()){
        auto[_,st]=q.top();q.pop();
        if(vis[st])continue;
        vis[st]=1;
        for(auto[val,nxt]:e){
            int ns=st^nxt;
            if(dis[ns]>dis[st]+val){
                dis[ns]=dis[st]+val;
                q.push({dis[ns],ns});
            }
        }
    }
    dis[15]=inf;
    for(int i=0;i<=15;i++){
        dis[15]=min(dis[15],dis[i]*2);
    }
    for(int i=0;i<N;i++)vis[i]=0;
    std::vector<i64> pre(1 << N), dp(1 << N, 1E12);
    dp[0] = 0;

    q.emplace(0, 0);
    while (!q.empty()) {
        auto [val, st] = q.top();
        q.pop();
        if(vis[st])continue;
        vis[st]=1;
        for (int i = 0; i < N; i++) {
            if (~st >> i) {
                int ns = st | (1 << i);
                int state=i^pre[st];
                if(state==15&&st!=0){
                    if(dp[ns]>dp[st]){
                        dp[ns]=dp[st];
                        pre[ns]=pre[st];
                        q.push({dp[ns],ns});
                        continue;
                    }
                }
                if(dp[ns]>dp[st]+dis[state]){
                    dp[ns]=dp[st]+dis[state];
                    pre[ns]=pre[st]^15^state;
                    q.push({dp[ns],ns});
                }
            }
        }
    }

    while (T--) {
        int n;
        std::cin >> n;
        std::vector<int> b(n);
        for (int i = 0; i < n; i++) {
            std::string t;
            std::cin >> t;
            b[i] = ((t[0] - '0') *8);
            b[i] += ((t[1] - '0') *4);
            std::cin >> t;
            b[i] += ((t[0] - '0') *2);
            b[i] += ((t[1] - '0'));
        }
        int state=0;
        for(int i=0;i<n;i++){
            state|=(1<<b[i]);
        }
        std::cout<<dp[state]<<'\n';
    }
    return 0;
}
源文件, 语言: C++20

詳細信息

Test #1:

score: 100
Accepted
time: 14ms
memory: 5680kb

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: 11ms
memory: 5312kb

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: 0
Accepted
time: 11ms
memory: 5292kb

input:

1 1000000 1000000 1000000 1000000
1
11
11

output:

2000000

result:

ok 1 number(s): "2000000"

Test #4:

score: -100
Wrong Answer
time: 22ms
memory: 5704kb

input:

10000 8 2 7 8
8
00
01

00
11

00
10

11
11

10
10

01
10

01
00

10
11
8
11
01

11
00

01
10

11
11

00
01

01
01

01
00

11
10
9
00
00

01
01

10
11

00
01

11
10

11
00

11
11

00
11

01
10
9
11
11

10
00

11
00

11
01

00
10

01
11

00
01

01
01

10
01
11
00
01

01
01

10
10

00
11

11
11

11
10
...

output:

34
32
36
37
42
36
42
38
40
42
36
44
34
39
39
32
29
39
40
40
38
41
46
38
31
38
37
38
34
35
32
41
34
36
41
40
45
34
39
34
29
36
40
40
43
35
39
38
38
38
42
29
41
41
36
42
44
40
41
35
42
40
38
33
34
39
38
37
42
40
34
36
29
34
35
38
36
39
38
37
36
38
35
34
36
34
42
40
38
40
40
40
38
42
38
29
36
40
36
36
...

result:

wrong answer 4th numbers differ - expected: '36', found: '37'
English 繁體中文 简体中文

伺服器時間: 2025-01-24 02:50:22 | 開源專案