제출 #1262291

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262291		SzymonKrzywda	Two Currencies (JOI23_currencies)	C++20	컴파일 에러	0 ms	0 KiB

currencies

#include <iostream>


using namespace std;
using vi = vector<int>;
using pii = pair<int, int>;

#define ff first
#define ss second
#define int long long


const int MAXN = 1e5 + 7;

struct LCA{
    int n, LOG, aktpre;
    vector<vi> graf;
    vector<vi> jump;
    vi preorder;
    vi depth;
    vi max_pre;

    void init(int N, vector<vi> kopia_graf) {
        graf = kopia_graf;
        n = N;
        LOG = ceil(log2(n)) + 1;
        jump.assign(n, vi(LOG, 0));
        depth.assign(n, 0);
        preorder.assign(n, 0);
        max_pre.assign(n, 0);
        aktpre = 0;
        dfs(0, 0);
        preprocess();
    }

    

    void dfs(int v, int p) {
        preorder[v] = aktpre++;
        max_pre[v] = preorder[v];
        jump[v][0] = p;
        for (int s : graf[v]) {
            if (p != s) {
                depth[s] = depth[v] + 1;
                dfs(s, v);
                max_pre[v] = max(max_pre[v], max_pre[s]);
            }
        }
    } 

    void preprocess() {
        for (int k = 1; k < LOG; k++) {
            for (int v = 0; v < n; v++) {
                jump[v][k] = jump[jump[v][k - 1]][k - 1];
            }
        }
    }

    int lca(int a, int b) {
        ////cout << "Szukam LCA: " << a << ' ' << b << '\n';
        if (a == b) return a;
        if (depth[a] < depth[b]) swap(a, b);

        for (int k = LOG - 1; k >= 0; k--) {
            if (depth[a] - (1 << k) >= depth[b]) a = jump[a][k];
        }
        //////cout << "O koniec 1\n";

        if (a == b) return a;

        for (int k = LOG - 1; k >= 0; k--) {
            if (jump[a][k] != jump[b][k]) {
                a = jump[a][k];
                b = jump[b][k];
            }
        }
       // ////cout << "O koniec 2\n";

        return jump[a][0];
    }
};

const int base = 1 << 17;
vector<int> tree;
vector<int> tree2;

void add(int l, int r, int val = 1) {
    l += base - 1;
    r += base + 1;

    while (l / 2 != r / 2) {
        if (l % 2 == 0) {
            tree[l + 1] += val;
            tree2[l + 1] ++;
        }
        if (r % 2 == 1) {
            tree[r - 1] += val;
            tree2[r - 1] ++;
        }
        l /= 2;
        r /= 2;
    }
}

pii query(int v) {
    v += base;
    int ans = 0;
    int ans2 = 0;
    while (v) {
        ans += tree[v];
        ans2 += tree2[v];
        v /= 2;
    }
    return {ans, ans2};
}


LCA lca;

struct zap{
    int a, b, g, s, idx, left, right, mid, koszts, ile;
};


bool comps(zap a, zap b) {
    return a.s < b.s;
}

bool comp_bin(zap a, zap b) {
    if (a.mid == b.mid) return a.idx < b.idx;
    return a.mid < b.mid;
}


int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, q, a, b;
    cin >> n >> m >> q;
    vector<vi> graf(n);
    vector<pii> kra;
    vi ile_bramek(n + 2, 0);

    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        a--;
        b--;
        graf[a].push_back(b);
        graf[b].push_back(a);
        kra.push_back({a, b});
    }
    lca.init(n, graf);
    vector<zap> tab_zap;

    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        a--;
        zap z;
        z.a = kra[a].first;
        z.b = kra[a].second;
        if (lca.depth[z.a] > lca.depth[z.b]) swap(z.a, z.b);
        ile_bramek[lca.preorder[z.b]] ++;
        ile_bramek[lca.max_pre[z.b] + 1] --;
        z.idx = -1;
        z.mid = b;
        z.s = b;
        tab_zap.push_back(z);
    }

    sort(tab_zap.begin(), tab_zap.end(), comps);
    for (int i = 0; i < m; i++) {
        tab_zap[i].mid = i;
    }

    for (int i = 1; i < n + 2; i++) ile_bramek[i] += ile_bramek[i - 1];
    
    for (int i = 0; i < q; i++) {
        zap z;
        cin >> z.a >> z.b >> z.g >> z.s;
        z.a--;
        z.b--;
        z.idx = i;
        z.left = -1;
        z.right = m - 1;
        z.mid = (z.left + z.right + 1) / 2;
        tab_zap.push_back(z);
    }   
    vi odp(q, -1);

    for (int i = 0; i < 21; i++) {
        //cout << "UWU\n";
        tree.assign(2 * base, 0);
        tree2.assign(2 * base, 0);
        sort(tab_zap.begin(), tab_zap.end(), comp_bin);

        for (auto & z : tab_zap) {
            //if (z.idx == -1) cout << "Dodaje bariere: " << z.a << ' ' << z.b << ' ' << z.g << ' ' << z.s << ' ' << z.mid << '\n';
            //else cout << "Zapytanie: " << z.a << ' ' << z.b << ' ' << z.idx << ' ' << z.left << ' ' << z.right << ' ' << z.mid << '\n';
            if (z.idx == -1) {
                add(lca.preorder[z.b], lca.max_pre[z.b], z.s);
            }
            else {
                int prea = lca.preorder[z.a];
                int preb = lca.preorder[z.b];
                int lcaa = lca.lca(z.a, z.b);
                int prelca = lca.preorder[lcaa];
                //cout << query(prea).first << ' ' << query(preb).first << ' ' << query(prelca).first << '\n';

                long long koszt = query(prea).first + query(preb).first - 2 * query(prelca).first;
                z.koszts = koszt;
                z.ile = ile_bramek[prea] + ile_bramek[preb] - 2 * ile_bramek[prelca] - (query(prea).second + query(preb).second - 2 * query(prelca).second);
                if (koszt <= z.s) z.left = z.mid;
                else z.right = z.mid - 1;
                z.mid = (z.left + z.right + 1) / 2;
               // cout << "KOSZT: " << koszt << ' ' << z.ile << '\n';
                
                if (z.left == -1 && z.right == -1) z.mid = -1;
                if (z.koszts <= z.s && z.ile <= z.g) odp[z.idx] = z.g - z.ile;
                else odp[z.idx] = -1;
            }
        }
    }
    
    for (int i = 0; i < q; i++) {
        cout << odp[i] << '\n';
    }
    

    return 0;
}


/*
3 2 1
2 1
3 2
2 1
1 1
1 2 1 1*/

컴파일 시 표준 에러 (stderr) 메시지

currencies.cpp:5:12: error: 'vector' does not name a type
    5 | using vi = vector<int>;
      |            ^~~~~~
currencies.cpp:17:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   17 |     vector<vi> graf;
      |            ^~
      |            void
currencies.cpp:17:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   17 |     vector<vi> graf;
      |            ^~
      |            void
currencies.cpp:17:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   17 |     vector<vi> graf;
      |            ^~
      |            void
currencies.cpp:17:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   17 |     vector<vi> graf;
      |            ^~
      |            void
currencies.cpp:17:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   17 |     vector<vi> graf;
      |            ^~
      |            void
currencies.cpp:17:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   17 |     vector<vi> graf;
      |            ^~
      |            void
currencies.cpp:17:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   17 |     vector<vi> graf;
      |            ^~
      |            void
currencies.cpp:17:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   17 |     vector<vi> graf;
      |            ^~
      |            void
currencies.cpp:17:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   17 |     vector<vi> graf;
      |            ^~
      |            void
currencies.cpp:17:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   17 |     vector<vi> graf;
      |            ^~
      |            void
currencies.cpp:17:5: error: 'vector' does not name a type
   17 |     vector<vi> graf;
      |     ^~~~~~
currencies.cpp:18:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   18 |     vector<vi> jump;
      |            ^~
      |            void
currencies.cpp:18:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   18 |     vector<vi> jump;
      |            ^~
      |            void
currencies.cpp:18:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   18 |     vector<vi> jump;
      |            ^~
      |            void
currencies.cpp:18:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   18 |     vector<vi> jump;
      |            ^~
      |            void
currencies.cpp:18:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   18 |     vector<vi> jump;
      |            ^~
      |            void
currencies.cpp:18:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   18 |     vector<vi> jump;
      |            ^~
      |            void
currencies.cpp:18:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   18 |     vector<vi> jump;
      |            ^~
      |            void
currencies.cpp:18:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   18 |     vector<vi> jump;
      |            ^~
      |            void
currencies.cpp:18:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   18 |     vector<vi> jump;
      |            ^~
      |            void
currencies.cpp:18:12: error: 'vi' was not declared in this scope; did you mean 'void'?
   18 |     vector<vi> jump;
      |            ^~
      |            void
currencies.cpp:18:5: error: 'vector' does not name a type
   18 |     vector<vi> jump;
      |     ^~~~~~
currencies.cpp:19:5: error: 'vi' does not name a type; did you mean 'void'?
   19 |     vi preorder;
      |     ^~
      |     void
currencies.cpp:20:5: error: 'vi' does not name a type; did you mean 'void'?
   20 |     vi depth;
      |     ^~
      |     void
currencies.cpp:21:5: error: 'vi' does not name a type; did you mean 'void'?
   21 |     vi max_pre;
      |     ^~
      |     void
currencies.cpp:23:29: error: 'vi' was not declared in this scope; did you mean 'void'?
   23 |     void init(int N, vector<vi> kopia_graf) {
      |                             ^~
      |                             void
currencies.cpp:23:29: error: 'vi' was not declared in this scope; did you mean 'void'?
   23 |     void init(int N, vector<vi> kopia_graf) {
      |                             ^~
      |                             void
currencies.cpp:23:29: error: 'vi' was not declared in this scope; did you mean 'void'?
   23 |     void init(int N, vector<vi> kopia_graf) {
      |                             ^~
      |                             void
currencies.cpp:23:29: error: 'vi' was not declared in this scope; did you mean 'void'?
   23 |     void init(int N, vector<vi> kopia_graf) {
      |                             ^~
      |                             void
currencies.cpp:23:22: error: 'vector' has not been declared
   23 |     void init(int N, vector<vi> kopia_graf) {
      |                      ^~~~~~
currencies.cpp:23:28: error: expected ',' or '...' before '<' token
   23 |     void init(int N, vector<vi> kopia_graf) {
      |                            ^
currencies.cpp: In member function 'void LCA::init(long long int, int)':
currencies.cpp:24:9: error: 'graf' was not declared in this scope
   24 |         graf = kopia_graf;
      |         ^~~~
currencies.cpp:24:16: error: 'kopia_graf' was not declared in this scope
   24 |         graf = kopia_graf;
      |                ^~~~~~~~~~
currencies.cpp:26:20: error: 'log2' was not declared in this scope
   26 |         LOG = ceil(log2(n)) + 1;
      |                    ^~~~
currencies.cpp:26:15: error: 'ceil' was not declared in this scope
   26 |         LOG = ceil(log2(n)) + 1;
      |               ^~~~
currencies.cpp:27:9: error: 'jump' was not declared in this scope
   27 |         jump.assign(n, vi(LOG, 0));
      |         ^~~~
currencies.cpp:27:24: error: 'vi' was not declared in this scope; did you mean 'void'?
   27 |         jump.assign(n, vi(LOG, 0));
      |                        ^~
      |                        void
currencies.cpp:28:9: error: 'depth' was not declared in this scope
   28 |         depth.assign(n, 0);
      |         ^~~~~
currencies.cpp:29:9: error: 'preorder' was not declared in this scope
   29 |         preorder.assign(n, 0);
      |         ^~~~~~~~
currencies.cpp:30:9: error: 'max_pre' was not declared in this scope
   30 |         max_pre.assign(n, 0);
      |         ^~~~~~~
currencies.cpp: In member function 'void LCA::dfs(long long int, long long int)':
currencies.cpp:39:9: error: 'preorder' was not declared in this scope
   39 |         preorder[v] = aktpre++;
      |         ^~~~~~~~
currencies.cpp:40:9: error: 'max_pre' was not declared in this scope
   40 |         max_pre[v] = preorder[v];
      |         ^~~~~~~
currencies.cpp:41:9: error: 'jump' was not declared in this scope
   41 |         jump[v][0] = p;
      |         ^~~~
currencies.cpp:42:22: error: 'graf' was not declared in this scope
   42 |         for (int s : graf[v]) {
      |                      ^~~~
currencies.cpp:44:17: error: 'depth' was not declared in this scope
   44 |                 depth[s] = depth[v] + 1;
      |                 ^~~~~
currencies.cpp: In member function 'void LCA::preprocess()':
currencies.cpp:54:17: error: 'jump' was not declared in this scope
   54 |                 jump[v][k] = jump[jump[v][k - 1]][k - 1];
      |                 ^~~~
currencies.cpp: In member function 'long long int LCA::lca(long long int, long long int)':
currencies.cpp:62:13: error: 'depth' was not declared in this scope
   62 |         if (depth[a] < depth[b]) swap(a, b);
      |             ^~~~~
currencies.cpp:65:17: error: 'depth' was not declared in this scope
   65 |             if (depth[a] - (1 << k) >= depth[b]) a = jump[a][k];
      |                 ^~~~~
currencies.cpp:65:54: error: 'jump' was not declared in this scope
   65 |             if (depth[a] - (1 << k) >= depth[b]) a = jump[a][k];
      |                                                      ^~~~
currencies.cpp:72:17: error: 'jump' was not declared in this scope
   72 |             if (jump[a][k] != jump[b][k]) {
      |                 ^~~~
currencies.cpp:79:16: error: 'jump' was not declared in this scope
   79 |         return jump[a][0];
      |                ^~~~
currencies.cpp: At global scope:
currencies.cpp:84:1: error: 'vector' does not name a type
   84 | vector<int> tree;
      | ^~~~~~
currencies.cpp:85:1: error: 'vector' does not name a type
   85 | vector<int> tree2;
      | ^~~~~~
currencies.cpp: In function 'void add(long long int, long long int, long long int)':
currencies.cpp:93:13: error: 'tree' was not declared in this scope; did you mean 'free'?
   93 |             tree[l + 1] += val;
      |             ^~~~
      |             free
currencies.cpp:94:13: error: 'tree2' was not declared in this scope
   94 |             tree2[l + 1] ++;
      |             ^~~~~
currencies.cpp:97:13: error: 'tree' was not declared in this scope; did you mean 'free'?
   97 |             tree[r - 1] += val;
      |             ^~~~
      |             free
currencies.cpp:98:13: error: 'tree2' was not declared in this scope
   98 |             tree2[r - 1] ++;
      |             ^~~~~
currencies.cpp: In function 'pii query(long long int)':
currencies.cpp:110:16: error: 'tree' was not declared in this scope; did you mean 'free'?
  110 |         ans += tree[v];
      |                ^~~~
      |                free
currencies.cpp:111:17: error: 'tree2' was not declared in this scope
  111 |         ans2 += tree2[v];
      |                 ^~~~~
currencies.cpp: In function 'int32_t main()':
currencies.cpp:141:12: error: 'vi' was not declared in this scope
  141 |     vector<vi> graf(n);
      |            ^~
currencies.cpp:141:5: error: 'vector' was not declared in this scope
  141 |     vector<vi> graf(n);
      |     ^~~~~~
currencies.cpp:2:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
    1 | #include <iostream>
  +++ |+#include <vector>
    2 | 
currencies.cpp:141:16: error: 'graf' was not declared in this scope
  141 |     vector<vi> graf(n);
      |                ^~~~
currencies.cpp:142:15: error: expected primary-expression before '>' token
  142 |     vector<pii> kra;
      |               ^
currencies.cpp:142:17: error: 'kra' was not declared in this scope
  142 |     vector<pii> kra;
      |                 ^~~
currencies.cpp:143:7: error: expected ';' before 'ile_bramek'
  143 |     vi ile_bramek(n + 2, 0);
      |       ^~~~~~~~~~~
      |       ;
currencies.cpp:154:15: error: expected primary-expression before '>' token
  154 |     vector<zap> tab_zap;
      |               ^
currencies.cpp:154:17: error: 'tab_zap' was not declared in this scope
  154 |     vector<zap> tab_zap;
      |                 ^~~~~~~
currencies.cpp:162:17: error: 'struct LCA' has no member named 'depth'
  162 |         if (lca.depth[z.a] > lca.depth[z.b]) swap(z.a, z.b);
      |                 ^~~~~
currencies.cpp:162:34: error: 'struct LCA' has no member named 'depth'
  162 |         if (lca.depth[z.a] > lca.depth[z.b]) swap(z.a, z.b);
      |                                  ^~~~~
currencies.cpp:163:9: error: 'ile_bramek' was not declared in this scope
  163 |         ile_bramek[lca.preorder[z.b]] ++;
      |         ^~~~~~~~~~
currencies.cpp:163:24: error: 'struct LCA' has no member named 'preorder'
  163 |         ile_bramek[lca.preorder[z.b]] ++;
      |                        ^~~~~~~~
currencies.cpp:164:24: error: 'struct LCA' has no member named 'max_pre'
  164 |         ile_bramek[lca.max_pre[z.b] + 1] --;
      |                        ^~~~~~~
currencies.cpp:176:37: error: 'ile_bramek' was not declared in this scope
  176 |     for (int i = 1; i < n + 2; i++) ile_bramek[i] += ile_bramek[i - 1];
      |                                     ^~~~~~~~~~
currencies.cpp:189:7: error: expected ';' before 'odp'
  189 |     vi odp(q, -1);
      |       ^~~~
      |       ;
currencies.cpp:193:9: error: 'tree' was not declared in this scope; did you mean 'free'?
  193 |         tree.assign(2 * base, 0);
      |         ^~~~
      |         free
currencies.cpp:194:9: error: 'tree2' was not declared in this scope
  194 |         tree2.assign(2 * base, 0);
      |         ^~~~~
currencies.cpp:201:25: error: 'struct LCA' has no member named 'preorder'
  201 |                 add(lca.preorder[z.b], lca.max_pre[z.b], z.s);
      |                         ^~~~~~~~
currencies.cpp:201:44: error: 'struct LCA' has no member named 'max_pre'
  201 |                 add(lca.preorder[z.b], lca.max_pre[z.b], z.s);
      |                                            ^~~~~~~
currencies.cpp:204:32: error: 'struct LCA' has no member named 'preorder'
  204 |                 int prea = lca.preorder[z.a];
      |                                ^~~~~~~~
currencies.cpp:205:32: error: 'struct LCA' has no member named 'preorder'
  205 |                 int preb = lca.preorder[z.b];
      |                                ^~~~~~~~
currencies.cpp:207:34: error: 'struct LCA' has no member named 'preorder'
  207 |                 int prelca = lca.preorder[lcaa];
      |                                  ^~~~~~~~
currencies.cpp:212:25: error: 'ile_bramek' was not declared in this scope
  212 |                 z.ile = ile_bramek[prea] + ile_bramek[preb] - 2 * ile_bramek[prelca] - (query(prea).second + query(preb).second - 2 * query(prelca).second);
      |                         ^~~~~~~~~~
currencies.cpp:219:54: error: 'odp' was not declared in this scope
  219 |                 if (z.koszts <= z.s && z.ile <= z.g) odp[z.idx] = z.g - z.ile;
      |                                                      ^~~
currencies.cpp:220:22: error: 'odp' was not declared in this scope
  220 |                 else odp[z.idx] = -1;
      |                      ^~~
currencies.cpp:226:17: error: 'odp' was not declared in this scope
  226 |         cout << odp[i] << '\n';
      |                 ^~~