QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#208366	#4235. Transparency	ucup-team1209^#	AC ✓	22ms	67216kb	C++20	2.9kb	2023-10-09 14:57:18	2023-10-09 14:57:19

Judging History

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

[2023-10-09 14:57:19]
评测

测评结果：AC
用时：22ms
内存：67216kb

查看

[2023-10-09 14:57:18]
提交

answer

#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using pi = pair <int, int> ; 

cs int N = 55; 
int n, m, P; 
bool ed[N];
vector <pi> e[N];
int id(char c) {
    if('A' <= c && c <= 'Z') return c - 'A' + 1;
    return c - 'a' + 27; 
}
int c[N][N][N][3], nd; 
cs int M = 2e6; 
bool fin[M]; 
int d[M], ex[M];
struct dat {
    int x, y, k, o;
}; 
vector <int> q[M];

void push(int t, int x) {
    if(d[x] > t) {
        d[x] = t;
        q[t].pb(x);
    }
}

int main() { 
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif
    cin >> n >> P >> m;
    for(int i = 1; i <= P; i++) {
        int x; 
        cin >> x;
        ed[x] = 1; 
    } 
    for(int i = 1; i <= m; i++) {
        int x; 
        char c[3];
        int y; 
        scanf("%d%s%d", & x, c, & y);
        e[x].pb({y, id(c[0])});
    }
    vector <dat> info; 
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
    for(int k = 0; k <= 26; k++)
    for(int o = 0; o < 3; o++) {
        c[i][j][k][o] = nd; 
        if(ed[i] && ed[j] && k == 0 && o) fin[nd] = 1; 
        info.pb({i, j, k, o});
        nd ++;
    }
    memset(d, 0x3f, sizeof d);
    q[0].pb(c[1][1][0][0]);
    d[c[1][1][0][0]] = 0;
    for(int t = 0; t < M; t++) 
    for(auto x : q[t]) {
        auto [i, j, k, o] = info[x]; 
        if(ex[x]) continue; ex[x] = 1; 
        if(fin[x]) {
            cout << t << '\n';
            return 0; 
        }
        if(o == 2) {
            assert(k == 0);
            for(auto [y, c2] : e[j]) 
            if(c2 > 26) push(t + 1, c[i][y][k][o]);
            continue; 
        }
        if(k == 0) {
            if(o == 0) {
                assert(i == j);
                for(auto [x, c1] : e[i])
                for(auto [y, c2] : e[j]) 
                if(c1 <= 26 && c2 > 26) {
                    push(t + 2, c[x][y][c1][1]);
                }
                for(auto [x, c1] : e[i])
                for(auto [y, c2] : e[j]) 
                if(c1 > 26 && c2 > 26 && c1 != c2) {
                    push(t + 2, c[x][y][0][1]);
                }
                for(auto [x, c1] : e[i])
                    push(t + 2, c[x][x][0][0]);
                for(auto [y, c2] : e[j]) 
                    if(c2 > 26) push(t + 1, c[i][y][k][2]);
            }
            for(auto [x, c1] : e[i])
            for(auto [y, c2] : e[j]) 
            if(c1 <= 26 && c2 <= 26 && c1 == c2) {
                push(t + 2, c[x][y][k][o]);
            }
        }
        else {
            assert(o);
            for(auto [y, c2] : e[j]) 
            if(c2 == k) push(t + 1, c[i][y][0][o]);
        }
        if(o) {
            for(auto [x, c1] : e[i]) 
            if(c1 > 26) push(t + 1, c[x][j][k][o]);
            for(auto [y, c2] : e[j]) 
            if(c2 > 26) push(t + 1, c[i][y][k][o]);
        }
    }
    cout << -1 << '\n';
    return 0; 
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 62860kb

input:

output:

result:

ok single line: '10'

Test #2:

score: 0

Accepted

time: 14ms

memory: 61024kb

input:

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0

Accepted

time: 4ms

memory: 61480kb

input:

output:

result:

ok single line: '4'

Test #4:

score: 0

Accepted

time: 7ms

memory: 61156kb

input:

output:

result:

ok single line: '24'

Test #5:

score: 0

Accepted

time: 7ms

memory: 61244kb

input:

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0

Accepted

time: 0ms

memory: 61244kb

input:

output:

result:

ok single line: '8'

Test #7:

score: 0

Accepted

time: 3ms

memory: 60832kb

input:

1 1 1
1
1 a 1

output:

result:

ok single line: '1'

Test #8:

score: 0

Accepted

time: 7ms

memory: 61660kb

input:

1 1 1
1
1 A 1

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0

Accepted

time: 5ms

memory: 60956kb

input:

output:

result:

ok single line: '2'

Test #10:

score: 0

Accepted

time: 3ms

memory: 60952kb

input:

output:

result:

ok single line: '1'

Test #11:

score: 0

Accepted

time: 4ms

memory: 61888kb

input:

output:

result:

ok single line: '4'

Test #12:

score: 0

Accepted

time: 4ms

memory: 66892kb

input:

output:

result:

ok single line: '288'

Test #13:

score: 0

Accepted

time: 3ms

memory: 65108kb

input:

output:

result:

ok single line: '533'

Test #14:

score: 0

Accepted

time: 12ms

memory: 67152kb

input:

output:

-1

result:

ok single line: '-1'

Test #15:

score: 0

Accepted

time: 4ms

memory: 67216kb

input:

output:

result:

ok single line: '1200'

Test #16:

score: 0

Accepted

time: 7ms

memory: 64888kb

input:

output:

result:

ok single line: '2'

Test #17:

score: 0

Accepted

time: 17ms

memory: 66144kb

input:

output:

-1

result:

ok single line: '-1'

Test #18:

score: 0

Accepted

time: 7ms

memory: 66436kb

input:

output:

result:

ok single line: '5'

Test #19:

score: 0

Accepted

time: 3ms

memory: 61892kb

input:

output:

result:

ok single line: '10'

Test #20:

score: 0

Accepted

time: 12ms

memory: 60444kb

input:

output:

-1

result:

ok single line: '-1'

Test #21:

score: 0

Accepted

time: 7ms

memory: 61480kb

input:

output:

result:

ok single line: '7'

Test #22:

score: 0

Accepted

time: 3ms

memory: 61444kb

input:

output:

result:

ok single line: '23'

Test #23:

score: 0

Accepted

time: 4ms

memory: 61024kb

input:

output:

result:

ok single line: '6'

Test #24:

score: 0

Accepted

time: 3ms

memory: 62516kb

input:

output:

result:

ok single line: '25'

Test #25:

score: 0

Accepted

time: 3ms

memory: 63020kb

input:

output:

result:

ok single line: '6'

Test #26:

score: 0

Accepted

time: 22ms

memory: 65060kb

input:

output:

-1

result:

ok single line: '-1'