Submission #1150079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150079		urosk	한자 끝말잇기 (JOI14_kanji)	C++20	0 / 100	34 ms	5192 KiB

Anna

#include "Annalib.h"
#include "bits/stdc++.h"
#define fi first
#define sc second
#define pb push_back
#define llinf 1000000000000000LL
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;

const ll maxn = 305;
ll n,m;
ll d[maxn][maxn];
ll d2[maxn][maxn];
ll last[maxn][maxn];
ll last2[maxn][maxn];
ll b[6][2];
bool vis[maxn*maxn];
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
    n = N,m = M;
    for(ll i = 0;i<K;i++) vis[U[i]] = 1;
    for(ll i = 1;i<=n;i++) {
        for(ll j = 1;j<=n;j++) d[i][j] = d2[i][j] = llinf;
    }
    for(ll i = 1;i<=n;i++) d[i][i] = d2[i][i] = 0;
    for(ll i = 1;i<=m;i++) {
        ll x = A[i-1]+1,y = B[i-1]+1;
        d[x][y] = d[y][x] = C[i-1];
        last[x][y] = last[y][x] = i-1;
        if(!vis[i-1]) {
            d2[x][y] = d2[y][x] = C[i-1];
            last2[x][y] = last2[y][x] = i-1;
        }
    }
    for(ll k = 1;k<=n;k++) {
        for(ll i = 1;i<=n;i++) {
            for(ll j = 1;j<=n;j++) {
                if(d[i][k]+d[k][j]<=d[i][j]) {
                    last[i][j] = last[k][j];
                    d[i][j] = d[i][k]+d[k][j];
                }
                if(d2[i][k]+d2[k][j]<=d2[i][j]) {
                    last[i][j] = last[k][j];
                    d2[i][j] = d2[i][k]+d2[k][j];
                }
            }
        }
    }
    ll c = -1;
    vector<ll> w;
    if(K==1) c = A[U[0]];
    else {
        map<ll,ll> mp;
        for(ll i = 0;i<K;i++) {
            mp[A[U[i]]]++;
            mp[B[U[i]]]++;
        }
        for(auto it : mp) {
            if(it.sc>0) c = it.fi;
        }
    }
    for(ll i = 0;i<K;i++) {
        w.pb(A[U[i]]^B[U[i]]^c+1);
    }
    c++;
    for(ll i = 0;i<Q;i++) {
        ll st = S[i]+1,en = T[i]+1;
        ll mask = 0;
        if(d[st][c]+d[c][en]==d[st][en]) {
            if(d2[st][c]+d2[c][en]==d[st][en]) {
                mask = 0;
            }else {
                for(ll j = 0;j<K;j++) {
                    ll e = w[j];

                    ll w = C[U[j]];
                    if(d2[st][e]+d2[c][en]+w==d[st][en]||d[st][c]+d2[e][en]+w==d[st][en]) mask = (1<<j);
                }
                for(ll j = 0;j<K;j++) {
                    for(ll f = 0;f<K;f++) {
                        if(f==j) continue;
                        ll e = w[j],r = w[f];
                        if(d2[st][e]+d2[r][en]+C[U[j]]+C[U[f]]==d[st][en]) mask = (1<<j)+(1<<f);
                    }
                }
            }
        }
        for(ll bit = 0;bit<=5;bit++) {
            if((1<<bit)&i) b[1][bit]|=mask;
            else b[0][bit]|=mask;
        }
    }
    for(ll i = 0;i<=5;i++) {
        for(ll j = 0;j<=5;j++) {
            if((1<<j)&b[0][i]) Tap(1);
            else Tap(0);
        }
        for(ll j = 0;j<=5;j++) {
            if((1<<j)&b[1][i]) Tap(1);
            else Tap(0);
        }
    }
}

Bruno

#include "Brunolib.h"
#include "bits/stdc++.h"
#define fi first
#define sc second
#define pb push_back
#define all(a) a.begin(),a.end()
#define llinf 1000000000000000LL
using namespace std;
using ll = long long;
using pll = pair<ll,ll>;

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[]) {
    ll n,m;
const ll maxn = 305;
ll d[maxn][maxn];
ll d2[maxn][maxn];
ll last[maxn][maxn];
ll last2[maxn][maxn];
ll b[6][2];

bool vis[maxn*maxn];
    n = N,m = M;
    for(ll i = 0;i<K;i++) vis[U[i]] = 1;
    for(ll i = 0;i<m;i++) vis[i] = 0;
    for(ll i = 0;i<K;i++) vis[U[i]] = 1;
    for(ll i = 1;i<=n;i++) {
        for(ll j = 1;j<=n;j++) d[i][j] = d2[i][j] = llinf;
    }
    for(ll i = 1;i<=n;i++) d[i][i] = d2[i][i] = 0;
    for(ll i = 1;i<=m;i++) {
        if(vis[i-1]) continue;
        ll x = A[i-1]+1,y = B[i-1]+1;
        d[x][y] = d[y][x] = C[i-1];
        last[x][y] = last[y][x] = i-1;
        if(!vis[i-1]) {
            d2[x][y] = d2[y][x] = C[i-1];
            last2[x][y] = last2[y][x] = i-1;
        }
    }
    for(ll k = 1;k<=n;k++) {
        for(ll i = 1;i<=n;i++) {
            for(ll j = 1;j<=n;j++) {
                if(d[i][k]+d[k][j]<d[i][j]) {
                    last[i][j] = last[k][j];
                    d[i][j] = d[i][k]+d[k][j];
                }
                if(d2[i][k]+d2[k][j]<d2[i][j]) {
                    last[i][j] = last[k][j];
                    d2[i][j] = d2[i][k]+d2[k][j];
                }
            }
        }
    }
    ll c = -1;
    vector<ll> w;
    if(K==1) c = A[U[0]];
    else {
        map<ll,ll> mp;
        for(ll i = 0;i<K;i++) {
            mp[A[U[i]]]++;
            mp[B[U[i]]]++;
        }
        for(auto it : mp) {
            if(it.sc>0) c = it.fi;
        }
    }
    for(ll i = 0;i<K;i++) {
        w.pb(A[U[i]]^B[U[i]]^c+1);
    }
    c++;
  ll csz = 0;
  for(ll i = 0;i<=5;i++) {
    b[0][i] = b[1][i] = 0;
    for(ll j = 0;j<=5;j++) {
      if(X[csz++]) b[0][i]+=(1<<j);
    }
    for(ll j = 0;j<=5;j++) {
      if(X[csz++]) b[1][i]+=(1<<j);
    }
  }
    for(ll j = 0;j<Q;j++) {
      ll mask = 63;
      for(ll bit = 0;bit<=5;bit++) {
        if((1<<bit)&j) {
          mask&=b[1][bit];
        }else mask&=b[0][bit];
      }
      ll st = S[j]+1,en = T[j]+1;
      if(mask==0){
        vector<ll> ans = {};
        while(st!=en){
            ans.pb(last[st][en]);
            ll id = last[st][en];
            en--;
            en = A[id]^B[id]^en;
            en++;
        }
        reverse(all(ans));
        for(ll x : ans) Answer(x);
      }else if(__builtin_popcount(mask)==1){
        ll e = -1;
        ll g = c;
        ll idi = -1;
        for(ll j = 0;j<=5;j++) if((1<<j)&mask) e = w[j],idi = U[j];
        if(d[st][e]+d[g][en]>d[st][g]+d[e][en]) swap(e,g);
        vector<ll> ans = {};
        //cerr<<"ab: "<<st<<" "<<e<< " "<<g<<" "<<en<< " "<<idi<<endl;
        while(st!=e){
            ans.pb(last[st][e]);
            ll id = last[st][e];
            e--;
            e = A[id]^B[id]^e;
            e++;
        }
        reverse(all(ans));
        vector<ll> ans2 = {};
        while(g!=en){
            ans2.pb(last[g][en]);
            ll id = last[g][en];
            en--;
            en = A[id]^B[id]^en;
            en++;
        }
        reverse(all(ans2));
        //cerr<<ans2.size()<<endl;
        //cerr<<ans.size()<<endl;
        for(ll x : ans) Answer(x);
        Answer(idi);
        for(ll x : ans2) Answer(x);
      }else{
        vector<ll> ve;
        vector<ll> ee;
        ll g = c;
        for(ll j = 0;j<=5;j++) if((1<<j)&mask) ve.pb(w[j]),ee.pb(j);
        if(d[st][ve[0]]+d[ve[1]][en]>d[st][ve[1]]+d[ve[0]][en]) swap(ve[0],ve[1]),swap(ee[0],ee[1]);
        vector<ll> ans = {};
        vector<ll> ans2 = {};
        ll e = ve[0];
        while(st!=e){
            ans.pb(last[st][e]);
            ll id = last[st][e];
            e--;
            e = A[id]^B[id]^e;
            e++;
        }
        reverse(all(ans));
        g = ve[1];
        while(g!=en){
            ans2.pb(last[g][en]);
            ll id = last[g][en];
            en--;
            en = A[id]^B[id]^en;
            en++;
        }
        reverse(all(ans2));
        for(ll x : ans) Answer(x);
        Answer(ee[0]);
        Answer(ee[1]);
        for(ll x : ans2) Answer(x);
      }
      Answer(-1);
    }

}

Compilation message (stderr)

# 2번째 컴파일 단계

Bruno.cpp: In function 'void Bruno(int, int, int*, int*, long long int*, int, int*, int*, int, int*, int, int*)':
Bruno.cpp:73:23: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
   73 |     b[0][i] = b[1][i] = 0;
      |               ~~~~~~~~^~~
Bruno.cpp:72:17: note: within this loop
   72 |   for(ll i = 0;i<=5;i++) {
      |                ~^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 22
• Subtask 3: 0 / 8
• Subtask 4: 0 / 40
• Subtask 5: 0 / 20