답안 #1009007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009007	2024-06-27T07:52:40 Z	GrindMachine	Spy 3 (JOI24_spy3)	C++17	92 / 100	142 ms	12984 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;
            }
        }

        rep(j,q){
            spl[T[j]] = 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	142 ms	12692 KB	Output is correct
2	Correct	0 ms	776 KB	Output is correct
3	Partially correct	88 ms	10264 KB	Partially correct
4	Partially correct	70 ms	9392 KB	Partially correct
5	Partially correct	108 ms	10568 KB	Partially correct
6	Partially correct	89 ms	10164 KB	Partially correct
7	Partially correct	92 ms	10168 KB	Partially correct
8	Partially correct	93 ms	10208 KB	Partially correct
9	Partially correct	66 ms	9132 KB	Partially correct
10	Correct	49 ms	9644 KB	Output is correct
11	Partially correct	92 ms	10292 KB	Partially correct
12	Correct	77 ms	10268 KB	Output is correct
13	Correct	90 ms	10244 KB	Output is correct
14	Correct	88 ms	10164 KB	Output is correct
15	Correct	66 ms	9736 KB	Output is correct
16	Correct	37 ms	9396 KB	Output is correct
17	Partially correct	75 ms	9580 KB	Partially correct
18	Partially correct	75 ms	9660 KB	Partially correct
19	Partially correct	115 ms	12368 KB	Partially correct
20	Partially correct	101 ms	12340 KB	Partially correct
21	Partially correct	116 ms	12360 KB	Partially correct
22	Partially correct	114 ms	12236 KB	Partially correct
23	Partially correct	89 ms	12220 KB	Partially correct
24	Partially correct	116 ms	12252 KB	Partially correct
25	Partially correct	99 ms	10236 KB	Partially correct
26	Partially correct	97 ms	10220 KB	Partially correct
27	Correct	0 ms	776 KB	Output is correct
28	Correct	94 ms	10488 KB	Output is correct
29	Partially correct	37 ms	7172 KB	Partially correct
30	Correct	90 ms	10676 KB	Output is correct
31	Correct	56 ms	10588 KB	Output is correct
32	Correct	97 ms	10796 KB	Output is correct
33	Correct	91 ms	10424 KB	Output is correct
34	Correct	85 ms	10800 KB	Output is correct
35	Correct	82 ms	10728 KB	Output is correct
36	Correct	81 ms	10816 KB	Output is correct
37	Correct	22 ms	5648 KB	Output is correct
38	Partially correct	39 ms	7216 KB	Partially correct
39	Correct	39 ms	7272 KB	Output is correct
40	Correct	19 ms	6836 KB	Output is correct
41	Partially correct	126 ms	12292 KB	Partially correct
42	Partially correct	76 ms	12484 KB	Partially correct
43	Correct	119 ms	12616 KB	Output is correct
44	Correct	49 ms	12332 KB	Output is correct
45	Partially correct	20 ms	5604 KB	Partially correct
46	Partially correct	30 ms	6936 KB	Partially correct
47	Correct	31 ms	7008 KB	Output is correct
48	Correct	0 ms	784 KB	Output is correct
49	Correct	0 ms	776 KB	Output is correct
50	Correct	79 ms	12488 KB	Output is correct
51	Partially correct	6 ms	1288 KB	Partially correct
52	Correct	0 ms	784 KB	Output is correct
53	Correct	126 ms	12984 KB	Output is correct
54	Partially correct	67 ms	8188 KB	Partially correct
55	Correct	75 ms	7988 KB	Output is correct
56	Partially correct	88 ms	12108 KB	Partially correct
57	Partially correct	121 ms	12044 KB	Partially correct
58	Partially correct	81 ms	9144 KB	Partially correct
59	Correct	125 ms	11956 KB	Output is correct
60	Partially correct	119 ms	11632 KB	Partially correct
61	Correct	119 ms	11740 KB	Output is correct
62	Correct	107 ms	10900 KB	Output is correct
63	Correct	124 ms	12064 KB	Output is correct
64	Correct	33 ms	9848 KB	Output is correct
65	Correct	53 ms	7240 KB	Output is correct
66	Correct	65 ms	12372 KB	Output is correct
67	Correct	60 ms	7288 KB	Output is correct
68	Correct	69 ms	12440 KB	Output is correct
69	Correct	0 ms	784 KB	Output is correct
70	Correct	0 ms	784 KB	Output is correct
71	Correct	0 ms	784 KB	Output is correct
72	Partially correct	22 ms	5404 KB	Partially correct
73	Partially correct	39 ms	6676 KB	Partially correct
74	Partially correct	41 ms	6656 KB	Partially correct
75	Correct	19 ms	6688 KB	Output is correct
76	Correct	0 ms	784 KB	Output is correct
77	Correct	108 ms	10060 KB	Output is correct
78	Partially correct	96 ms	10312 KB	Partially correct
79	Correct	87 ms	10168 KB	Output is correct
80	Correct	0 ms	776 KB	Output is correct
81	Correct	106 ms	10364 KB	Output is correct
82	Partially correct	100 ms	10228 KB	Partially correct
83	Correct	96 ms	10164 KB	Output is correct