답안 #1008934

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008934	2024-06-27T05:57:09 Z	GrindMachine	Spy 3 (JOI24_spy3)	C++17	92 / 100	149 ms	12968 KB

Aoi

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/127315?#comment-1131129

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "Aoi.h"

namespace {

    int variable_example = 0;

    int function_example(int a, int b) { return a + b; }

}  // namespace

std::string aoi(int n, int m, int q, int k, std::vector<int> A,
                std::vector<int> B, std::vector<long long> C,
                std::vector<int> T, std::vector<int> X) {
    
    // n = #of nodes, m = #of edges
    // A,B,C = edges of graph
    // q = #of query cities
    // T = query cities
    // k = #of deleted edges
    // X = ids of deleted edges

    vector<pll> adj1[n];
    vector<vector<ll>> adj2(n);
    map<pll,ll> mp;

    rep(i,m){
        ll u = A[i], v = B[i], w = C[i];
        adj1[u].pb({v,w}), adj1[v].pb({u,w});
        mp[{u,v}] = mp[{v,u}] = i;
    }

    // build sp tree
    priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>> pq;
    pq.push({0,0,-1});
    vector<ll> par(n,-1);
    vector<bool> vis(n);
    vector<ll> depth(n);

    while(!pq.empty()){
        auto [dis,u,p] = pq.top();
        pq.pop();

        if(vis[u]) conts;
        vis[u] = 1;
        par[u] = p;
        if(p != -1){
            depth[u] = depth[p]+1;
            adj2[p].pb(u);
        }

        // cout << p << " " << u << endl;

        for(auto [v,w] : adj1[u]){
            pq.push({dis+w,v,u});
        }
    }

    // calc tin,tout
    vector<ll> tin(n), tout(n);
    ll timer = 0;

    auto dfs1 = [&](ll u, auto &&dfs1) -> void{
        tin[u] = timer++;
        trav(v,adj2[u]){
            dfs1(v,dfs1);
        }
        tout[u] = timer-1;
    };

    dfs1(0,dfs1);

    auto is_ances = [&](ll u, ll v){
        return tin[u] <= tin[v] and tout[u] >= tout[v];
    };

    auto get_lca = [&](ll u, ll v){
        // cout << u << " " << v << " ";
        while(u != v){
            if(depth[u] < depth[v]) swap(u,v);
            u = par[u];
        }

        // cout << u << endl;
        return u;
    };

    // find the nodes of the virtual tree
    vector<pll> nodes;
    nodes.pb({0,0});
    rep(i,q){
        ll u = T[i];
        nodes.pb({tin[u],u});
    }

    sort(all(nodes));
    nodes.resize(unique(all(nodes))-nodes.begin());
    ll initial_size = sz(nodes);

    rep(i,initial_size-1){
        ll lca = get_lca(nodes[i].ss,nodes[i+1].ss);
        nodes.pb({tin[lca],lca});
    }

    sort(all(nodes));
    nodes.resize(unique(all(nodes))-nodes.begin());
    assert(sz(nodes) <= 2*q);

    // for(auto [ti,u] : nodes){
    //     cout << ti << " " << u << endl;
    // }
    
    // build the virtual tree + construct walk
    stack<ll> stk;
    vector<ll> pv(n,-1);
    vector<ll> node_id(n,-1);
    stk.push(0);
    node_id[0] = 0;
    string walk = "";
    ll ptr = 1;
    rep1(i,sz(nodes)-1){
        ll u = nodes[i].ss;
        node_id[u] = ptr++;
        while(!is_ances(stk.top(),u)){
            stk.pop();
            walk.pb('0');
        }
        pv[u] = stk.top();
        stk.push(u);
        walk.pb('1');
    }

    while(!stk.empty()){
        stk.pop();
        walk.pb('0');
    }
    assert(sz(walk) == 2*sz(nodes)-1);
    
    // for each edge in the sp tree, find the virtual edge that it belongs to
    vector<ll> idv(m,2*q-1);
    rep1(i,sz(nodes)-1){
        ll u = nodes[i].ss;
        ll incoming_edge = node_id[u]-1;
        assert(incoming_edge >= 0);
        ll ppv = pv[u];

        while(u != ppv){
            ll p = par[u];
            ll id = mp[{u,p}];
            idv[id] = incoming_edge;
            u = p;
        }
    }

    // for each deleted edge, encode the edge in the virtual tree that it belongs to
    string edge_encoding = "";
    rep(i,k){
        ll curr_id = idv[X[i]];
        rev(bit,4,0){
            ll b = 0;
            if(curr_id&(1<<bit)) b = 1;
            edge_encoding.pb(char('0'+b));
        }
    }

    // for each query node, encode it's corresponding node in the virtual tree
    string node_encoding = "";
    rep(i,q){
        ll curr_id = node_id[T[i]];
        assert(curr_id != -1);

        rev(bit,4,0){
            ll b = 0;
            if(curr_id&(1<<bit)) b = 1;
            node_encoding.pb(char('0'+b));
        }
    }

    string s = walk+edge_encoding+node_encoding;
    return s;

    // string s = "";

    // rep(i,q){
    //     ll u = T[i];
    //     vector<ll> path;
    //     while(u){
    //         path.pb(u);
    //         u = par[u];
    //     }
    //     path.pb(0);
        
    //     vector<ll> edges;
    //     rep(j,sz(path)-1){
    //         pll px = {path[j],path[j+1]};
    //         edges.pb(mp[px]);
    //     }

    //     sort(all(edges));

    //     rep(j,k){
    //         ll id = X[j];
    //         if(binary_search(all(edges),id)){
    //             s.pb('1');
    //         }
    //         else{
    //             s.pb('0');
    //         }
    //     }
    // }

    // return s;

    // variable_example++;
    // variable_example = function_example(1, 2);
    // std::string s(100, '0');
    // s[0] = '1';
    // return s;
}

Bitaro

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/127315?#comment-1131129

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "Bitaro.h"

namespace {

    int variable_example = 0;

    int function_example(int a, int b) { return a + b; }

}  // namespace

void bitaro(int n, int m, int q, int k, std::vector<int> A, std::vector<int> B,
            std::vector<long long> C, std::vector<int> T, std::vector<int> X,
            std::string s) {

    // n = #of nodes, m = #of edges
    // A,B,C = edges of graph (edge weights of deleted edges = -1)
    // q = #of query cities
    // T = query cities
    // k = #of deleted edges
    // X = ids of deleted edges
    // s = received string

    vector<pll> adj[n];
    map<pll,ll> mp;

    rep(i,m){
        ll u = A[i], v = B[i], w = C[i];
        adj[u].pb({v,w}), adj[v].pb({u,w});
        mp[{u,v}] = mp[{v,u}] = i;
    }

    // recover the walk
    ll ptr = 0;
    stack<ll> stk;
    vector<ll> pv;
    pv.pb(-1);
    ll curr_node = 0;

    while(curr_node != -1){
        char ch = s[ptr++];
        if(ch == '1'){
            pv.pb(curr_node);
            curr_node = sz(pv)-1;
        }
        else{
            curr_node = pv[curr_node];
        }
    }

    // recover the virtual edge that each deleted edge belongs to
    vector<ll> idv(k,-1);
    rep(i,k){
        ll mask = 0;
        rep(bit,5){
            mask = (mask<<1)|(s[ptr++]-'0');
        }

        idv[i] = mask;
    }

    rep(i,q){
        // recover the corresponding node of T[i] in the virtual tree
        ll src = 0;
        rep(bit,5){
            src = (src<<1)|(s[ptr++]-'0');
        }

        vector<bool> good(2*q);
        ll curr_node = src;

        while(curr_node){
            good[curr_node-1] = 1;
            curr_node = pv[curr_node];
        }

        vector<bool> spl(n); 
        vector<bool> on_path(m);

        rep(j,k){
            ll id = X[j];
            if(good[idv[j]]){
                on_path[id] = 1;
                spl[A[id]] = spl[B[id]] = 1;
            }
        }

        priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>> pq;
        pq.push({0,0,-1});
        vector<ll> par(n,-1);
        vector<bool> vis(n);

        while(!pq.empty()){
            auto [dis,u,p] = pq.top();
            pq.pop();

            if(vis[u]) conts;
            vis[u] = 1;
            par[u] = p;

            if(spl[u]){
                ll cnt = 0;
                for(auto [v,w] : adj[u]){
                    ll id = mp[{u,v}];
                    if(w == -1 and on_path[id]){
                        cnt++;
                    }
                }

                if(cnt){
                    while(!pq.empty()){
                        pq.pop();
                    }   

                    for(auto [v,w] : adj[u]){
                        ll id = mp[{u,v}];
                        if(w == -1 and on_path[id]){
                            on_path[id] = 0;
                            pq.push({0,v,u});
                        }
                    }

                    conts;
                }
            }

            for(auto [v,w] : adj[u]){
                if(w == -1) conts;
                pq.push({dis+w,v,u});
            }
        }

        vector<ll> nodes;
        ll u = T[i];
        while(u){
            assert(u != -1);
            nodes.pb(u);
            u = par[u];
        }
        nodes.pb(0);
        reverse(all(nodes));

        vector<int> ans;
        rep(j,sz(nodes)-1){
            pll px = {nodes[j],nodes[j+1]};
            ans.pb(mp[px]);
        }

        answer(ans);

        // trav(x,ans) cout << x << " ";
        // cout << endl;
    }

    // variable_example++;
    // variable_example = function_example(1, 2);
    // for (int i = 0; i < q; i++) {
    //     std::vector<int> v(10);
    //     for (int j = 0; j < 10; j++) {
    //         v[j] = j;
    //     }
    //     answer(v);
    // }
}

Compilation message

Aoi.cpp:67:9: warning: 'int {anonymous}::function_example(int, int)' defined but not used [-Wunused-function]
   67 |     int function_example(int a, int b) { return a + b; }
      |         ^~~~~~~~~~~~~~~~
Aoi.cpp:65:9: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   65 |     int variable_example = 0;
      |         ^~~~~~~~~~~~~~~~

Bitaro.cpp:67:9: warning: 'int {anonymous}::function_example(int, int)' defined but not used [-Wunused-function]
   67 |     int function_example(int a, int b) { return a + b; }
      |         ^~~~~~~~~~~~~~~~
Bitaro.cpp:65:9: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   65 |     int variable_example = 0;
      |         ^~~~~~~~~~~~~~~~

Subtask #1

92.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	135 ms	12828 KB	Output is correct
2	Correct	1 ms	776 KB	Output is correct
3	Partially correct	86 ms	10260 KB	Partially correct
4	Partially correct	69 ms	9504 KB	Partially correct
5	Partially correct	111 ms	10436 KB	Partially correct
6	Partially correct	89 ms	10160 KB	Partially correct
7	Partially correct	92 ms	10200 KB	Partially correct
8	Partially correct	89 ms	10164 KB	Partially correct
9	Partially correct	67 ms	9188 KB	Partially correct
10	Correct	46 ms	9580 KB	Output is correct
11	Partially correct	100 ms	10196 KB	Partially correct
12	Correct	84 ms	10176 KB	Output is correct
13	Correct	96 ms	10360 KB	Output is correct
14	Correct	104 ms	10160 KB	Output is correct
15	Correct	78 ms	9588 KB	Output is correct
16	Correct	37 ms	9396 KB	Output is correct
17	Partially correct	80 ms	9512 KB	Partially correct
18	Partially correct	84 ms	9716 KB	Partially correct
19	Partially correct	134 ms	12356 KB	Partially correct
20	Partially correct	118 ms	12300 KB	Partially correct
21	Partially correct	125 ms	12352 KB	Partially correct
22	Partially correct	134 ms	12484 KB	Partially correct
23	Partially correct	96 ms	12216 KB	Partially correct
24	Partially correct	124 ms	12216 KB	Partially correct
25	Partially correct	114 ms	10236 KB	Partially correct
26	Partially correct	109 ms	10268 KB	Partially correct
27	Correct	1 ms	776 KB	Output is correct
28	Correct	97 ms	10164 KB	Output is correct
29	Partially correct	37 ms	7352 KB	Partially correct
30	Correct	80 ms	10672 KB	Output is correct
31	Correct	56 ms	10660 KB	Output is correct
32	Correct	109 ms	10672 KB	Output is correct
33	Correct	105 ms	10284 KB	Output is correct
34	Correct	101 ms	10668 KB	Output is correct
35	Correct	96 ms	10700 KB	Output is correct
36	Correct	98 ms	10676 KB	Output is correct
37	Correct	26 ms	5556 KB	Output is correct
38	Partially correct	49 ms	7192 KB	Partially correct
39	Correct	47 ms	7192 KB	Output is correct
40	Correct	22 ms	6936 KB	Output is correct
41	Partially correct	130 ms	12280 KB	Partially correct
42	Partially correct	86 ms	12532 KB	Partially correct
43	Correct	138 ms	12508 KB	Output is correct
44	Correct	51 ms	12012 KB	Output is correct
45	Partially correct	25 ms	5636 KB	Partially correct
46	Partially correct	33 ms	6844 KB	Partially correct
47	Correct	40 ms	6636 KB	Output is correct
48	Correct	1 ms	788 KB	Output is correct
49	Correct	0 ms	1284 KB	Output is correct
50	Correct	91 ms	12696 KB	Output is correct
51	Partially correct	6 ms	1296 KB	Partially correct
52	Correct	2 ms	776 KB	Output is correct
53	Correct	139 ms	12968 KB	Output is correct
54	Partially correct	68 ms	8156 KB	Partially correct
55	Correct	89 ms	8032 KB	Output is correct
56	Partially correct	103 ms	12088 KB	Partially correct
57	Partially correct	137 ms	12052 KB	Partially correct
58	Partially correct	103 ms	9104 KB	Partially correct
59	Correct	149 ms	11740 KB	Output is correct
60	Partially correct	141 ms	11644 KB	Partially correct
61	Correct	133 ms	11776 KB	Output is correct
62	Correct	123 ms	11000 KB	Output is correct
63	Correct	123 ms	12056 KB	Output is correct
64	Correct	39 ms	9848 KB	Output is correct
65	Correct	52 ms	7140 KB	Output is correct
66	Correct	65 ms	12452 KB	Output is correct
67	Correct	57 ms	7324 KB	Output is correct
68	Correct	74 ms	12692 KB	Output is correct
69	Correct	0 ms	776 KB	Output is correct
70	Correct	0 ms	784 KB	Output is correct
71	Correct	2 ms	776 KB	Output is correct
72	Partially correct	20 ms	5400 KB	Partially correct
73	Partially correct	49 ms	6720 KB	Partially correct
74	Partially correct	45 ms	6668 KB	Partially correct
75	Correct	22 ms	6664 KB	Output is correct
76	Correct	1 ms	776 KB	Output is correct
77	Correct	97 ms	10276 KB	Output is correct
78	Partially correct	107 ms	10196 KB	Partially correct
79	Correct	106 ms	10164 KB	Output is correct
80	Correct	1 ms	720 KB	Output is correct
81	Correct	104 ms	10400 KB	Output is correct
82	Partially correct	102 ms	10232 KB	Partially correct
83	Correct	96 ms	10168 KB	Output is correct