Submission #676049

#TimeUsernameProblemLanguageResultExecution timeMemory
676049CookieMonthly railway pass (LMIO18_menesinis_bilietas)C++14
100 / 100
192 ms31948 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; ifstream fin("talent.in"); ofstream fout("talent.out"); #define ll long long #define vt vector #define pb push_back #define fi first #define se second #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define pii pair<int, int> #define pll pair<ll, ll> //#define int long long typedef unsigned long long ull; const int mxn = 5e5 + 3; int n, m; vt<pii>edge; vt<int>g[mxn + 1]; bool ok[mxn + 1], ans[mxn + 1]; struct DSU{ int p[mxn + 1]; void init(){ for(int i = 1; i <= n; i++)p[i] = -1; } int fp(int a){ if(p[a] < 0)return(a); return(p[a] = fp(p[a])); } void unon(int a, int b){ a = fp(a); b = fp(b); if(a == b)return; if(-p[a] < -p[b])swap(a, b); p[a] += p[b]; p[b] = a; return; } }; DSU dsu; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; dsu.init(); forr(i, 0, m){ int u, v; cin >> u >> v; char c; cin >> c; if(c == 'A'){ edge.pb({u, v}); }else{ dsu.unon(u, v); } } int cnt = 0; for(int i = 1; i <= n; i++){ if(dsu.p[i] < 0)cnt++; } for(auto [u, v]: edge){ u = dsu.fp(u); v = dsu.fp(v); if(u != v){ g[u].pb(v); g[v].pb(u); } //cout << u << ' ' << v << " "; } for(int i = 1; i <= n; i++){ if(dsu.p[i] < 0){ int curr =0; for(auto j: g[i]){ if(!ok[j]){ ok[j] = true; curr++; } } ans[i] = ((curr + 1) == cnt); for(auto j: g[i])ok[j] = false; } } int res =0; for(int i = 1; i <= n; i++){ res += ans[dsu.fp(i)]; } cout << res; return 0; }

Compilation message (stderr)

menesinis_bilietas.cpp: In function 'int main()':
menesinis_bilietas.cpp:61:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |     for(auto [u, v]: edge){
      |              ^
#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...