제출 #640880

#제출 시각아이디문제언어결과실행 시간메모리
640880pls33Monthly railway pass (LMIO18_menesinis_bilietas)C++17
6 / 100
312 ms36700 KiB
#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; #pragma region dalykai using p32 = pair<int, int>; using p32u = pair<uint32_t, uint32_t>; using p64 = pair<int64_t, int64_t>; using p64u = pair<uint64_t, uint64_t>; using vi16 = vector<int16_t>; using vi16u = vector<uint16_t>; using vi32 = vector<int>; using vi32u = vector<uint32_t>; using vi64 = vector<int64_t>; using vi64u = vector<uint64_t>; using vp32 = vector<p32>; using vp32u = vector<p32u>; using vp64 = vector<p64>; using vp64u = vector<p64u>; using vvi32 = vector<vi32>; using vvi32u = vector<vi32u>; using vvi64 = vector<vi64>; using vvi64u = vector<vi64u>; using vvp32 = vector<vp32>; using vvp32u = vector<vp32u>; using vvp64 = vector<vp64>; using vvp64u = vector<vp64u>; using pf32 = pair<float, float>; using pf64 = pair<double, double>; using pf80 = pair<long double, long double>; using vf32 = vector<float>; using vf64 = vector<double>; using vf80 = vector<long double>; using vpf32 = vector<pf32>; using vpf64 = vector<pf64>; using vpf80 = vector<pf80>; using vvf32 = vector<vf32>; using vvf64 = vector<vf64>; using vvf80 = vector<vf80>; using vvpf32 = vector<vpf32>; using vvpf64 = vector<vpf64>; using vvpf80 = vector<vpf80>; template <typename key, typename val> using ord_map = tree<key, val, less<key>, rb_tree_tag, tree_order_statistics_node_update>; template <typename key> using ord_set = tree<key, null_type, less<key>, rb_tree_tag, tree_order_statistics_node_update>; const int BUF_SZ = 1 << 15; inline namespace fast_in { char buf[BUF_SZ]; int pos; int len; char next_char(FILE *f) { if (pos == len) { pos = 0; len = (int)fread(buf, 1, BUF_SZ, f); if (!len) { return EOF; } } return buf[pos++]; } int read_int(FILE *f) { int x; char ch; int sgn = 1; while (!isdigit(ch = next_char(f))) { if (ch == '-') { sgn *= -1; } } x = ch - '0'; while (isdigit(ch = next_char(f))) { x = x * 10 + (ch - '0'); } return x * sgn; } } /** * @brief gale programos flush_out kviest!! */ inline namespace fast_out { char buf[BUF_SZ]; int pos; void flush_out(FILE *f) { fwrite(buf, 1, pos, f); pos = 0; } void write_char(char c, FILE *f) { if (pos == BUF_SZ) { flush_out(f); } buf[pos++] = c; } void write_int(int x, FILE *f) { static char num_buf[100]; if (x < 0) { write_char('-', f); x *= -1; } int len = 0; for (; x >= 10; x /= 10) { num_buf[len++] = (char)('0' + (x % 10)); } write_char((char)('0' + x), f); while (len) { write_char(num_buf[--len], f); } write_char('\n', f); } } #pragma endregion struct dsu_t { vi32 parent, rank; dsu_t(int n) : parent(n), rank(n, 1) { iota(parent.begin(), parent.end(), 0); } int find(int i) { if (parent[i] == i) { return i; } return parent[i] = find(parent[i]); } void set_union(int a, int b) { a = find(a); b = find(b); if (a == b) { return; } if (rank[b] > rank[a]) { swap(a, b); } parent[b] = a; rank[a] += rank[b]; } }; int main() { #ifndef _AAAAAAAAA ios_base::sync_with_stdio(false); cin.tie(0); #else freopen("bilietas.in", "r", stdin); #ifndef __linux__ atexit([]() { freopen("con", "r", stdin); system("pause"); }); #endif #endif int v, e; cin >> v >> e; dsu_t dsu(v); vp32 bus; for (size_t i = 0; i < e; i++) { int a, b; char type; cin >> a >> b >> type; a--; b--; if (type == 'A') { bus.emplace_back(a, b); } else { dsu.set_union(a, b); } } vvi32 adj(v); for (auto &b : bus) { b.first = dsu.find(b.first); b.second = dsu.find(b.second); if (b.first == b.second) { continue; } adj[b.first].push_back(b.second); adj[b.second].push_back(b.first); } int count = 0; for (int i = 0; i < adj.size(); i++) { auto &next = adj[i]; if (next.size()) { sort(next.begin(), next.end()); auto it = unique(next.begin(), next.end()); next.erase(it, next.end()); int cur = dsu.rank[i]; for (auto &a : next) { cur += dsu.rank[a]; } count += (cur == v) * dsu.rank[i]; } } cout << count << '\n'; return 0; }

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

menesinis_bilietas.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
menesinis_bilietas.cpp:151: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
  151 | #pragma endregion
      | 
menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:211:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  211 |     for (size_t i = 0; i < e; i++)
      |                        ~~^~~
menesinis_bilietas.cpp:245:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  245 |     for (int i = 0; i < adj.size(); i++)
      |                     ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...