oj.uz

Submission #925470

# Submission time Handle Problem Language Result Execution time Memory
925470 2024-02-11T17:41:51 Z bachhoangxuan 한자 끝말잇기 (JOI14_kanji) C++17
100 / 100
 109 ms 17992 KB 
#include "Annalib.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 305;
const int maxm = maxn*maxn;
const ll inf = 4e18;
ll dist[maxn][maxn];
bool check[maxm];

void Anna(int N, int M, int A[], int B[], ll C[], int Q, int S[], int T[], int K, int U[]) {
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) dist[i][j]=inf;
    for(int i=0;i<K;i++) check[U[i]]=true;
    for(int i=0;i<M;i++){
        if(!check[i]) dist[A[i]][B[i]]=C[i];
    }
    for(int i=0;i<N;i++) dist[i][i]=0;
    for(int k=0;k<N;k++){
        for(int i=0;i<N;i++) for(int j=0;j<N;j++) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
    }
    vector<vector<int>> g(K+1);
    for(int i=0;i<Q;i++) g[0].push_back(i);
    auto f = [&](int s,int t,int id){
        if(id==K) return dist[s][t];
        else return min(inf,dist[s][A[U[id]]]+dist[B[U[id]]][t]);
    };
    vector<pair<int,int>> p;
    for(int i=1;i<=K;i++){
        ll c=(i==K?0:C[U[i]]);
        for(int j=0;j<i;j++){
            sort(g[j].begin(),g[j].end(),[f,S,T,i,j](int x,int y){
                ll dx=f(S[x],T[x],i)-f(S[x],T[x],j);
                ll dy=f(S[y],T[y],i)-f(S[y],T[y],j);
                return dx<dy;
            });
            ll dd=C[U[j]]-c;
            int pos=0;
            while(pos<(int)g[j].size()){
                int x=g[j][pos];
                ll dx=f(S[x],T[x],i)-f(S[x],T[x],j);
                if(dx<=dd) pos++;
                else break;
            }
            p.push_back({pos,(int)g[j].size()+1});
            for(int k=0;k<pos;k++) g[i].push_back(g[j][k]);
            g[j].erase(g[j].begin(),g[j].begin()+pos);
        }
    }
    __int128 total=0;
    for(int i=(int)p.size()-1;i>=0;i--) total=total*p[i].second+p[i].first;
    while(total) Tap(total&1),total/=2;
}

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

#define ll long long
const int maxn = 305;
const int maxm = maxn*maxn;
const ll inf = 4e18;
ll dist[maxn][maxn];
bool check[maxm];

int w[maxn][maxn];
void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) {
    __int128 total=0;
    for(int i=L-1;i>=0;i--) total=total*2+X[i];

    for(int i=0;i<N;i++) for(int j=0;j<N;j++) w[i][j]=-1,dist[i][j]=inf;
    for(int i=0;i<K;i++) check[U[i]]=true;
    for(int i=0;i<M;i++){
        if(!check[i]){
            dist[A[i]][B[i]]=C[i];
            w[A[i]][B[i]]=i;
        }
    }
    for(int i=0;i<N;i++) dist[i][i]=0;
    for(int k=0;k<N;k++){
        for(int i=0;i<N;i++) for(int j=0;j<N;j++) dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
    }
    int cur=0;
    vector<vector<int>> g(K+1);
    for(int i=0;i<Q;i++) g[0].push_back(i);
    auto f = [&](int s,int t,int id){
        if(id==K) return dist[s][t];
        else return min(inf,dist[s][A[U[id]]]+dist[B[U[id]]][t]);
    };
    for(int i=1;i<=K;i++){
        for(int j=0;j<i;j++){
            sort(g[j].begin(),g[j].end(),[f,S,T,i,j](int x,int y){
                ll dx=f(S[x],T[x],i)-f(S[x],T[x],j);
                ll dy=f(S[y],T[y],i)-f(S[y],T[y],j);
                return dx<dy;
            });
            int pos=total%((int)g[j].size()+1);
            total/=((int)g[j].size()+1);
            for(int k=0;k<pos;k++) g[i].push_back(g[j][k]);
            g[j].erase(g[j].begin(),g[j].begin()+pos);
        }
    }
    vector<int> num(Q,-1);
    for(int i=0;i<=K;i++) for(int x:g[i]) num[x]=i;
    function<void(int,int)> path = [&](int s,int t){
        if(s==t) return;
        for(int u=0;u<N;u++){
            if(w[s][u]==-1) continue;
            if(C[w[s][u]]+dist[u][t]==dist[s][t]){
                Answer(w[s][u]);
                return path(u,t);
            }
        }
    };
    for(int i=0;i<Q;i++){
        int id=num[i];
        //cout << i << ' ' << id << '\n';
        if(id<K){
            path(S[i],A[U[id]]);
            Answer(U[id]);
            path(B[U[id]],T[i]);
        }
        else path(S[i],T[i]);
        Answer(-1);
    }
}

Compilation message

Bruno.cpp: In function 'void Bruno(int, int, int*, int*, long long int*, int, int*, int*, int, int*, int, int*)':
Bruno.cpp:29:9: warning: unused variable 'cur' [-Wunused-variable]
   29 |     int cur=0;
      |         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 9252 KB Output is correct - L = 25
2 Correct 49 ms 9252 KB Output is correct - L = 19
3 Correct 54 ms 9284 KB Output is correct - L = 24
4 Correct 50 ms 9248 KB Output is correct - L = 20
5 Correct 53 ms 9260 KB Output is correct - L = 23
6 Correct 50 ms 9252 KB Output is correct - L = 23
7 Correct 49 ms 9228 KB Output is correct - L = 25
8 Correct 51 ms 9260 KB Output is correct - L = 0
9 Correct 50 ms 9632 KB Output is correct - L = 4
10 Correct 52 ms 9536 KB Output is correct - L = 0
11 Correct 54 ms 9180 KB Output is correct - L = 4
12 Correct 105 ms 17728 KB Output is correct - L = 18
13 Correct 51 ms 9216 KB Output is correct - L = 5
14 Correct 48 ms 9236 KB Output is correct - L = 1

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 9376 KB Output is correct - L = 53
2 Correct 51 ms 9364 KB Output is correct - L = 60
3 Correct 49 ms 9528 KB Output is correct - L = 52
4 Correct 51 ms 9400 KB Output is correct - L = 54
5 Correct 51 ms 9212 KB Output is correct - L = 60
6 Correct 52 ms 9252 KB Output is correct - L = 59
7 Correct 50 ms 9276 KB Output is correct - L = 45
8 Correct 50 ms 9264 KB Output is correct - L = 61
9 Correct 52 ms 9232 KB Output is correct - L = 61
10 Correct 51 ms 9292 KB Output is correct - L = 61
11 Correct 51 ms 9196 KB Output is correct - L = 62
12 Correct 50 ms 9444 KB Output is correct - L = 30
13 Correct 109 ms 17992 KB Output is correct - L = 33
14 Correct 49 ms 9252 KB Output is correct - L = 59
15 Correct 51 ms 9188 KB Output is correct - L = 52
16 Correct 52 ms 9524 KB Output is correct - L = 16
17 Correct 56 ms 9592 KB Output is correct - L = 14
18 Correct 54 ms 9868 KB Output is correct - L = 31
19 Correct 49 ms 9276 KB Output is correct - L = 31
20 Correct 55 ms 10400 KB Output is correct - L = 55
21 Correct 56 ms 10212 KB Output is correct - L = 30
22 Correct 50 ms 9268 KB Output is correct - L = 62
23 Correct 52 ms 9448 KB Output is correct - L = 61
24 Correct 52 ms 9268 KB Output is correct - L = 61

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 9372 KB Output is correct - L = 53
2 Correct 51 ms 9336 KB Output is correct - L = 60
3 Correct 51 ms 9424 KB Output is correct - L = 52
4 Correct 51 ms 9456 KB Output is correct - L = 54
5 Correct 54 ms 9292 KB Output is correct - L = 60
6 Correct 49 ms 9284 KB Output is correct - L = 59
7 Correct 51 ms 9440 KB Output is correct - L = 45
8 Correct 56 ms 9348 KB Output is correct - L = 61
9 Correct 55 ms 9268 KB Output is correct - L = 61
10 Correct 50 ms 9384 KB Output is correct - L = 61
11 Correct 51 ms 9424 KB Output is correct - L = 62
12 Correct 49 ms 9276 KB Output is correct - L = 30
13 Correct 106 ms 17832 KB Output is correct - L = 33
14 Correct 50 ms 9188 KB Output is correct - L = 59
15 Correct 49 ms 9440 KB Output is correct - L = 52
16 Correct 52 ms 9324 KB Output is correct - L = 16
17 Correct 52 ms 9668 KB Output is correct - L = 14
18 Correct 54 ms 9852 KB Output is correct - L = 31
19 Correct 50 ms 9260 KB Output is correct - L = 31
20 Correct 60 ms 10224 KB Output is correct - L = 55
21 Correct 56 ms 10132 KB Output is correct - L = 30
22 Correct 57 ms 9416 KB Output is correct - L = 62
23 Correct 50 ms 9268 KB Output is correct - L = 61
24 Correct 50 ms 9276 KB Output is correct - L = 61

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 9180 KB Output is correct - L = 53
2 Correct 50 ms 9588 KB Output is correct - L = 60
3 Correct 51 ms 9404 KB Output is correct - L = 52
4 Correct 50 ms 9248 KB Output is correct - L = 54
5 Correct 50 ms 9276 KB Output is correct - L = 60
6 Correct 51 ms 9280 KB Output is correct - L = 59
7 Correct 51 ms 9272 KB Output is correct - L = 45
8 Correct 50 ms 9148 KB Output is correct - L = 61
9 Correct 51 ms 9656 KB Output is correct - L = 61
10 Correct 50 ms 9512 KB Output is correct - L = 61
11 Correct 51 ms 9268 KB Output is correct - L = 62
12 Correct 55 ms 9276 KB Output is correct - L = 30
13 Correct 106 ms 17720 KB Output is correct - L = 33
14 Correct 49 ms 9252 KB Output is correct - L = 59
15 Correct 49 ms 9260 KB Output is correct - L = 52
16 Correct 56 ms 9508 KB Output is correct - L = 16
17 Correct 53 ms 9576 KB Output is correct - L = 14
18 Correct 54 ms 9852 KB Output is correct - L = 31
19 Correct 54 ms 9188 KB Output is correct - L = 31
20 Correct 56 ms 10256 KB Output is correct - L = 55
21 Correct 60 ms 10148 KB Output is correct - L = 30
22 Correct 52 ms 9196 KB Output is correct - L = 62
23 Correct 51 ms 9388 KB Output is correct - L = 61
24 Correct 53 ms 9280 KB Output is correct - L = 61

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 9448 KB Output is correct - L = 53
2 Correct 51 ms 9396 KB Output is correct - L = 60
3 Correct 50 ms 9268 KB Output is correct - L = 52
4 Correct 50 ms 9384 KB Output is correct - L = 54
5 Correct 50 ms 9252 KB Output is correct - L = 60
6 Correct 56 ms 9376 KB Output is correct - L = 59
7 Correct 50 ms 9400 KB Output is correct - L = 45
8 Correct 51 ms 9460 KB Output is correct - L = 61
9 Correct 55 ms 9472 KB Output is correct - L = 61
10 Correct 51 ms 9200 KB Output is correct - L = 61
11 Correct 51 ms 9280 KB Output is correct - L = 62
12 Correct 51 ms 9404 KB Output is correct - L = 30
13 Correct 106 ms 17812 KB Output is correct - L = 33
14 Correct 50 ms 9180 KB Output is correct - L = 59
15 Correct 55 ms 9444 KB Output is correct - L = 52
16 Correct 52 ms 9524 KB Output is correct - L = 16
17 Correct 54 ms 9552 KB Output is correct - L = 14
18 Correct 55 ms 9872 KB Output is correct - L = 31
19 Correct 52 ms 9264 KB Output is correct - L = 31
20 Correct 59 ms 10404 KB Output is correct - L = 55
21 Correct 56 ms 10132 KB Output is correct - L = 30
22 Correct 51 ms 9428 KB Output is correct - L = 62
23 Correct 53 ms 9464 KB Output is correct - L = 61
24 Correct 50 ms 9472 KB Output is correct - L = 61