Submission #1870261
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int maxn = 2e5 + 20; int n, m, comp1, comp2, cnt; vector<int> g[maxn]; bool vis[maxn]; ll C (int a) { return 1ll * a * (a-1) / 2; } void dfs (int v) { vis[v] = true; cnt ++; for (int i : g[v]) if (!vis[i]) dfs (i); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; g[--a].pb(--b); g[b].pb(a); } dfs (0); comp1 = cnt; cnt = 0; dfs (1); comp2 = cnt; if (comp1 < comp2) swap (comp1, comp2); comp1 += n - (comp1 + comp2); cout << C (comp1) + C (comp2) - m << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Shock |
User | mahan_sh |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 724 Byte |
Status | AC |
Exec Time | 37 ms |
Memory | 11264 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | a01, a02, a03 |
All | a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
a01 | AC | 3 ms | 4992 KB |
a02 | AC | 3 ms | 4992 KB |
a03 | AC | 3 ms | 4992 KB |
b04 | AC | 3 ms | 4992 KB |
b05 | AC | 3 ms | 4992 KB |
b06 | AC | 30 ms | 11264 KB |
b07 | AC | 29 ms | 9728 KB |
b08 | AC | 16 ms | 8064 KB |
b09 | AC | 30 ms | 11264 KB |
b10 | AC | 28 ms | 8064 KB |
b11 | AC | 3 ms | 4992 KB |
b12 | AC | 33 ms | 7680 KB |
b13 | AC | 37 ms | 8320 KB |
b14 | AC | 37 ms | 8320 KB |
b15 | AC | 37 ms | 8320 KB |
b16 | AC | 36 ms | 8320 KB |
b17 | AC | 34 ms | 7936 KB |
b18 | AC | 21 ms | 6144 KB |
b19 | AC | 20 ms | 6144 KB |
b20 | AC | 4 ms | 5120 KB |
b21 | AC | 7 ms | 5248 KB |
b22 | AC | 33 ms | 7808 KB |
b23 | AC | 36 ms | 8064 KB |