제출 #425024

#제출 시각아이디문제언어결과실행 시간메모리
425024CodePlatinaCollapse (JOI18_collapse)C++17
컴파일 에러
0 ms0 KiB
#include <iostream> #include <vector> #include <algorithm> #include <utility> #include <tuple> #include <map> #include <set> #include <cstdlib> #include <unordered_set> #define pii pair<int, int> #define piii pair<int, pii> #define pll pair<long long, long long> #define plll pair<long long, pll> #define tiii tuple<int, int, int> #define tiiii tuple<int, int, int, int> #define ff first #define ss second #define ee ss.ff #define rr ss.ss #define DEBUG #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma") const int INF = (int)1e9 + 7; const int Q = 600; using namespace std; vector<pii> eg; vector<pii> lf; map<pii, int> M; vector<int> lsu[101010]; vector<int> lsd[101010]; vector<pii> qr[101010]; struct UF { int par[101010]; short rnk[101010]; int pnt; int cnt, __cnt; vector<pii> rec; UF(void) : pnt(0), cnt(0), __cnt(0), rec() { for(int i = 0; i < 101010; ++i) par[i] = i, rnk[i] = 0; } int fnd(int x) { return x == par[x] ? x : fnd(par[x]); } void uni(int x, int y) { x = fnd(x), y = fnd(y); if(x == y) return; if(rnk[x] == rnk[y]) { rec.push_back({0, x}); rec.push_back({1, y}); ++rnk[x]; par[y] = x; } else if(rnk[x] > rnk[y]) { rec.push_back({1, y}); par[y] = x; } else { rec.push_back({1, x}); par[x] = y; } ++cnt; } void save(void) { pnt = (int)rec.size(); __cnt = cnt; } void rollback(void) { while((int)rec.size() > pnt) { auto [c, x] = rec.back(); if(c == 0) --rnk[x]; else par[x] = x; rec.pop_back(); } cnt = __cnt; } }uf[200]; vector<int> ind[200]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m, T; cin >> n >> m >> T; for(int i = 0; i < m; ++i) { int c, x, y; cin >> c >> x >> y; if(x > y) swap(x, y); if(c == 0) { M[{x, y}] = (int)eg.size(); eg.push_back({x, y}); lf.push_back({i, m}); } else { lf[M[{x, y}]].ss = i; M.erase({x, y}); } } for(int i = 0; i < (int)eg.size(); ++i) { if(eg[i].ff > 0) lsd[eg[i].ff - 1].push_back(i); lsu[eg[i].ss].push_back(i); } for(int i = 0; i < T; ++i) { int x, y; cin >> x >> y; qr[y].push_back({x, i}); } vector<int> ans(T); for(auto &i : ans) i = n; for(int i = 0; i < n; ++i) { for(int k = 0; k < (int)lsu[i].size(); ++k) { auto [x, y] = eg[lsu[i][k]]; auto [s, e] = lf[lsu[i][k]]; for(int j = s / Q; j <= (e - 1) / Q; ++j) { int l = j * Q, r = l + Q; if(s <= l && r <= e) uf[j].uni(x, y); else ind[j].push_back(lsu[i][k]); } } for(auto [t, q] : qr[i]) { int j = t / Q; uf[j].save(); for(int k = 0; k < (int)ind[j].size(); ++k) { auto [x, y] = eg[ind[j][k]]; auto [s, e] = lf[ind[j][k]]; if(s <= t && t < e) uf[j].uni(x, y); } ans[q] -= uf[j].cnt; uf[j].rollback(); } } for(int i = 0; i <= m / Q; ++i) { uf[i].pnt = uf[i].cnt = uf[i].__cnt = 0; uf[i].rollback(); ind[i].clear(); ind[i].shrink_to_fit(); } for(int i = n - 1; i >= 0; --i) { for(int k = 0; k < (int)lsd[i].size(); ++k) { auto [x, y] = eg[lsd[i][k]]; auto [s, e] = lf[lsd[i][k]]; for(int j = s / Q; j <= (e - 1) / Q; ++j) { int l = j * Q, r = l + Q; if(s <= l && r <= e) uf[j].uni(x, y); else ind[j].push_back(lsd[i][k]); } } for(auto [t, q] : qr[i]) { int j = t / Q; uf[j].save(); for(int k = 0; k < (int)ind[j].size(); ++k) { auto [x, y] = eg[ind[j][k]]; auto [s, e] = lf[ind[j][k]]; if(s <= t && t < e) uf[j].uni(x, y); } ans[q] -= uf[j].cnt; uf[j].rollback(); } } for(int i = 0; i < T; ++i) cout << ans[i] << '\n'; }

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

/usr/bin/ld: /tmp/ccBE04q2.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccbMhWZ2.o:collapse.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccBE04q2.o: in function `main':
grader.cpp:(.text.startup+0x227): undefined reference to `simulateCollapse(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status