제출 #863534

#제출 시각아이디문제언어결과실행 시간메모리
863534Cyber_WolfA Difficult(y) Choice (BOI21_books)C++17
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define lg long long #define mid (lr+hr)/2 const lg N = 2e5+5; vector<array<lg, 2>> adj[N]; lg head[N], in[N], out[N], tmp, sz[N], p[N], euler[N], co[N], loc[N], depth[N]; struct Node{ lg f; lg l; bool inc; bool dec; Node() { f = l = 0; inc = dec = 0; } } seg[N << 2]; //cost, first, last, increase, decrease Node fake() { Node e; e.f = -1; return e; } Node merge(Node a, Node b) { if(a.f == -1) return b; if(b.f == -1) return a; Node c; c.f = a.f; c.l = b.l; c.inc = (a.inc && b.inc && a.l < b.f); c.dec = (a.dec && b.dec && a.l > b.f); return c; } void build(lg node, lg lr, lg hr) { if(lr == hr) { seg[node].inc = seg[node].dec = 1; return; } build(node << 1, lr, mid); build(node << 1 | 1, mid+1, hr); seg[node] = merge(seg[node << 1], seg[node << 1 | 1]); return; } void update(lg node, lg lr, lg hr, lg idx, lg val) { if(lr > idx || hr < idx) return ; if(lr == hr) { seg[node].f = seg[node].l = val; return ; } update(node << 1, lr, mid, idx, val); update(node << 1 | 1, mid+1, hr, idx, val); seg[node] = merge(seg[node << 1], seg[node << 1 | 1]); return; } Node get(lg node, lg lr, lg hr, lg lq, lg hq) { if(lq > hr || lr > hq) return fake(); if(lq <= lr && hr <= hq) return seg[node]; return merge(get(node << 1, lr, mid, lq, hq), get(node << 1 | 1, mid+1, hr, lq, hq)); } void dfs(lg src, lg par = -1) { sz[src] = 1; for(auto [it, c] : adj[src]) { if(it == par) continue; depth[it] = depth[src]+1; p[it] = src; co[it] = c; dfs(it, src); sz[src] += sz[it]; } return ; } void dfs2(lg src, lg par = -1) { in[src] = ++tmp; euler[tmp] = src; loc[src] = tmp; if(p[src] == adj[src][0][0]) reverse(adj[src].begin(), adj[src].end()); for(auto &it : adj[src]) { if(it[0] == par) { continue; } if(sz[it[0]] > sz[adj[src][0][0]]) swap(adj[src][0], it); } for(auto [it, c] : adj[src]) { if(it == par) { continue; } head[it] = (it == adj[src][0][0] ? head[src] : it); dfs2(it, src); } out[src] = tmp; } lg lca(lg a, lg b) { while(head[a] != head[b]) { if(depth[b] > depth[a]) swap(a, b); a = p[head[a]]; } if(depth[b] > depth[a]) swap(a, b); return b; } int main() { #ifdef CYBER freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif lg n, k; cin >> n >> k; vector<array<lg, 3>> que; lg id = 1; k += n-1; while(k--) { char c; cin >> c; if(c == 'S') { lg u, v; cin >> u >> v; que.push_back({c, u, v}); adj[u].push_back({v, id}); adj[v].push_back({u, id}); id++; } else if(c == 'Q') { lg u, v; cin >> u >> v; que.push_back({c, u, v}); } else{ lg u; cin >> u; que.push_back({c, u, 0}); } } dfs(1); head[1] = 1; p[1] = 1; dfs2(1); // cout << "head in out sz p co depth loc\n"; // for(int i = 1; i <= n; i++) // { // cout << head[i] << ' ' << in[i] << ' ' << out[i] << ' ' << sz[i] << ' ' << p[i] << ' ' << co[i] << ' ' << depth[i] << ' ' << loc[i] << '\n'; // } // for(int i = 1; i <= n; i++) cout << euler[i] << ' '; // cout << '\n'; // for(int i = 1; i <= n; i++) // { // for(int j = 1; j <= n; j++) // { // cout << lca(i, j) << ' '; // } // cout << '\n'; // } build(1, 1, n); for(auto [c, a, b] : que) { // cout << c << ' ' << a << ' ' << b << '\n'; if(c == 'S') { if(p[a] == b) swap(a, b); update(1, 1, n, loc[b], co[b]); } else if(c == 'Q') { lg _lca = lca(a, b); lg cur = 1; while(head[b] != head[_lca] && cur) { cur &= get(1, 1, n, loc[head[b]], loc[b]).inc; b = p[head[b]]; } cur &= get(1, 1, n, loc[_lca], loc[b]).inc; while(head[a] != head[_lca] && cur) { cur &= get(1, 1, n, loc[head[a]], loc[a]).dec; a = p[head[a]]; } cur &= get(1, 1, n, loc[_lca], loc[a]).dec; cout << (cur ? "yes\n" : "no\n"); } } }

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

/usr/bin/ld: /tmp/ccEA7wV3.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cciM3fk8.o:books.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccEA7wV3.o: in function `main':
grader.cpp:(.text.startup+0x83): undefined reference to `solve(int, int, long long, int)'
collect2: error: ld returned 1 exit status