Submission #1305012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305012		Zbyszek99	Spy 3 (JOI24_spy3)	C++20	100 / 100	187 ms	5908 KiB

Aoi

#include "Aoi.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const ll INF = 1e16+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

namespace {
vector<pii> graph[10001];
ll costs[20001];
pii up_vert[10001];
int color[20001];
bool odw[10001];
bool is_special[20001];
int path_beg[17];
int path_end[17];
int color_cnt[17];
int special_ind[20001];
ll dist[10001];
int n,m,q,k;
int dead_group = 16;

string ans;

void add_int(int x, int s)
{
    rep(i,s)
    {
        if(x & (1 << i)) ans += '1';
        else ans += '0';
    }
}

void dijkstra()
{
    priority_queue<pair<ll,pair<int,pii>>,vector<pair<ll,pair<int,pii>>>,greater<pair<ll,pair<int,pii>>>> pq;
    pq.push({0,{0,{-1,-1}}});
    while(!pq.empty())
    {
        pair<ll,pair<int,pii>> t = pq.top();
        pq.pop();
        if(odw[t.ss.ff]) continue;
        odw[t.ss.ff] = 1;
        dist[t.ss.ff] = t.ff;
        up_vert[t.ss.ff] = t.ss.ss;
        forall(it,graph[t.ss.ff])
        {
            pq.push({t.ff+costs[it.ss],{it.ff,{t.ss.ff,it.ss}}});
        }
    }
}

void swap_groups(int a, int b)
{
    if(a == dead_group) dead_group = b;
    else if(b == dead_group) dead_group = a;
    swap(path_beg[a],path_beg[b]);
    rep(i,m)
    {
        if(color[i] == a) color[i] = b;
        else if(color[i] == b) color[i] = a;
    }
    swap(color_cnt[a],color_cnt[b]);
}

}

// swap(T,X)
string aoi(int N, int M, int Q, int K, vi A, vi B, vl C, vi X, vi T) 
{
    n = N; m = M; q = Q; k = K;
    sort(all(T));
    rep(i,m)
    {
        costs[i] = C[i];
        color[i] = 16;
        graph[A[i]].pb({B[i],i});
        graph[B[i]].pb({A[i],i});
    }
    rep(i,17) path_beg[i] = -1;
    rep(i,17) path_end[i] = -1;
    int cur = 0;
    rep(i,k) 
    {
        is_special[T[i]] = 1;
        special_ind[T[i]] = cur++;
    }
    dijkstra();
    rep(i,q)
    {
        int v = X[i];
        while(v != 0)
        {
            if(is_special[up_vert[v].ss])
            {
                if(path_end[i] == -1) path_end[i] = up_vert[v].ss;
                if(color[up_vert[v].ss] == 16) color[up_vert[v].ss] = i;
                else
                {
                    path_beg[i] = up_vert[v].ss;
                    break;
                }
            } 
            v = up_vert[v].ff;
        }
    }
    rep(i,k) color_cnt[color[T[i]]]++;
    pii best = {1e9,-1};
    rep(i,17) best = min(best,{color_cnt[i],i});
    if(best.ss != 16) swap_groups(best.ss,16);
    best = {1e9,-1};
    rep(i,16) best = min(best,{color_cnt[i],i});
    if(best.ss != 0) swap_groups(best.ss,0);
    rep(i,k) add_int(color[T[i]],4);
    add_int(dead_group,5);
    rep(i,k) if(color[T[i]] % 16 == 0)
    {
        add_int(color[T[i]] == 16,1);
    }
    rep(i,17) add_int((path_beg[i] != -1 ? special_ind[path_beg[i]] : 301),9);
    rep(i,q) add_int((path_end[i] != -1 ? special_ind[path_end[i]] : 301),9);
    return ans;
}

Bitaro

#include "Bitaro.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const ll INF = 1e16+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

namespace {
vector<pii> graph[10001];
ll costs[20001];
int color[20001];
int path_beg[17];
pair<int,vi> root_path[10001];
int rel_end[20001];
bool was[17];
int n,m,q,k;
int dead_group = 16;
pii up_vert[10001];
ll dist[10001];
vi A,B;

string ans;
int cur_poz = 0;

int get_int(int s)
{
    int x = 0;
    rep(i,s) if(ans[cur_poz++] == '1') x += (1<<i);
    return x;
}

void dijkstra(int x)
{
    priority_queue<pair<ll,pair<int,pii>>,vector<pair<ll,pair<int,pii>>>,greater<pair<ll,pair<int,pii>>>> pq;
    pq.push({0,{x,{-1,0}}});
    rep(i,n) dist[i] = -1;
    while(!pq.empty())
    {
        pair<ll,pair<int,pii>> t = pq.top();
        pq.pop();
        if(dist[t.ss.ff] != -1) continue;
        dist[t.ss.ff] = t.ff;
        up_vert[t.ss.ff] = t.ss.ss;
        forall(it,graph[t.ss.ff])
        {
            pq.push({t.ff+costs[it.ss],{it.ff,{t.ss.ff,it.ss}}});
        }
    }
}

vi get_path(int v, int beg)
{
    vi path;
    while(v != beg && v != -1)
    {
        path.pb(up_vert[v].ss);
        v = up_vert[v].ff;
    }
    return path;
}

void add_path(int beg, vi x)
{
    forall(it,x) costs[it] = 0;
    dijkstra(beg);
    forall(it,x) costs[it] = INF;
    forall(it,x)
    {
        if(up_vert[A[it]].ff == B[it]) rel_end[it] = A[it];
        else rel_end[it] = B[it];
        int v = rel_end[it];
        root_path[v] = {beg,get_path(v,beg)};
    }
}


}

//swap(T,X)
void bitaro(int N, int M, int Q, int K, vi A2, vi B2, vl C, vi X, vi T, string S) 
{
    A = A2;
    B = B2;
    ans = S;
    n = N; m = M; q = Q; k = K;
    sort(all(T));
    rep(i,m)
    {
        costs[i] = C[i];
        color[i] = 18;
        graph[A[i]].pb({B[i],i});
        graph[B[i]].pb({A[i],i});
        rel_end[i] = -1;
    }
    int cur = 0;
    rep(i,k) 
    {
        costs[T[i]] = INF;
    }
    while(siz(T) != 302) T.pb(-1);
    rep(i,k) color[T[i]] = get_int(4);
    dead_group = get_int(5);
    rep(i,m) if(color[i] == 18) color[i] = dead_group;
    rep(i,k) if(color[T[i]] % 16 == 0)
    {
        if(get_int(1)) color[T[i]] = 16;
    }
    rep(i,17) 
    {
        path_beg[i] = get_int(9);
        if(path_beg[i] == 301) path_beg[i] = -1;
        else path_beg[i] = T[path_beg[i]];
    }
    while(true)
    {
        int x = -1;
        rep(j,17)
        {
            if(j == dead_group || was[j]) continue;
            if(path_beg[j] == -1 || rel_end[path_beg[j]] != -1) x = j;
        }
        if(x == -1) break;
        was[x] = 1;
        vi path;
        rep(i,k) if(color[T[i]] == x) path.pb(T[i]);
        if(siz(path) == 0) continue;
        add_path((path_beg[x] != -1 ? rel_end[path_beg[x]] : 0),path);
    }
    rep(i,q)
    {
        int p = get_int(9);
        int beg = 0;
        if(p != 301) beg = rel_end[T[p]];
        int v = X[i];
        dijkstra(beg);
        vi ans = get_path(v,beg);
        v = beg;
        while(v != 0)
        {
            forall(it,root_path[v].ss) ans.pb(it);
            v = root_path[v].ff;
        }
        reverse(all(ans));
        answer(ans);
        
    }
}

• Subtask 1: 100 / 100