Submission #630330

#TimeUsernameProblemLanguageResultExecution timeMemory
630330pooyashamsMaking Friends on Joitter is Fun (JOI20_joitter2)C++14
0 / 100
1 ms340 KiB
#include <algorithm> #include <iostream> #include <numeric> #include <cstring> #include <iomanip> #include <vector> #include <bitset> #include <stack> #include <queue> #include <cmath> #include <set> #include <map> #define endl '\n' #define X first #define Y second using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; const int maxn = 2012; int sz[maxn]; int root[maxn]; int get_root(int x) { if(root[x] == x) return x; return get_root(root[x]); } inline bool mrg(int x, int y) { x = get_root(x); y = get_root(y); if(x == y) return false; if(sz[x] < sz[y]) swap(x, y); root[y] = x; sz[x] += sz[y]; return true; } pii edgs[maxn]; bool vis[maxn][maxn]; inline int get_ans(int n) { int ans = 0; for(int i = 0; i < n; i++) { if(root[i] == i) { ans += sz[i]*(sz[i]-1); } } vector<pii> rms; for(int i = 0; i < n; i++) { int x = edgs[i].X; int y = get_root(edgs[i].Y); if(get_root(x) == y) continue; if(vis[x][y]) continue; vis[x][y] = true; rms.push_back(pii(x, y)); ans += sz[y]; //cerr << "adding sz " << x << " " << y << endl; } for(pii p: rms) vis[p.X][p.Y] = false; return ans; } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; iota(root, root+n, 0); fill(sz, sz+n, 1); for(int i = 0; i < m; i++) { int x, y; cin >> x >> y; x--; y--; edgs[i] = pii(x, y); // int rx = get_root(x); int ry = get_root(y); if(rx != ry) { bool pos = false; for(int j = 0; j < i; j++) { int a = edgs[j].X; int b = edgs[j].Y; if(get_root(a) == ry and get_root(b) == rx) pos = true; } if(pos) mrg(rx, ry); } //for(int j = 0; j < n; j++) // cerr << get_root(j) << " "; //cerr << endl; // cout << get_ans(i+1) << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...