제출 #872694

#제출 시각아이디문제언어결과실행 시간메모리
872694Ghulam_JunaidPipes (CEOI15_pipes)C++17
0 / 100
944 ms50520 KiB
/* #include <bits/stdc++.h> using namespace std; const int N = 1e4 + 3; int n, m; bool edge[N][N], vis[N]; vector<vector<int>> comps; vector<int> independent; int main(){ cin >> n >> m; for (int i=0; i<m; i++){ int u, v; cin >> u >> v; edge[u][v] = 1; edge[v][u] = 1; } for (int sz = n; sz > 0; sz--){ string s; for (int i=0; i<n-sz; i++) s += '0'; for (int i=0; i<sz; i++) s += '1'; do { bool done = 0; for (int i=0; i<n; i++){ if (s[i] == '1' and vis[i+1]){ done = 1; break; } } if (done) continue; for (int v = 1; v <= n; v++){ for (int u = v + 1; u <= n; u++){ if (s[v - 1] == '1' and s[u - 1] == '1' and edge[v][u]) done = 1; } } if (done) continue; for (int i=0; i<n; i++){ if (s[i] == '1'){ independent.push_back(i+1); vis[i+1] = 1; } } comps.push_back(independent); independent.clear(); } while (next_permutation(s.begin(), s.end())); } cout << comps.size() << endl; for (auto x : comps){ for (auto v : x) cout << v << " "; cout << endl; } } */ /* ./a.out < input_000.txt > output_000.txt ./a.out < input_001.txt > output_001.txt ./a.out < input_002.txt > output_002.txt ./a.out < input_003.txt > output_003.txt ./a.out < input_005.txt > output_005.txt ./a.out < input_006.txt > output_006.txt ./a.out < input_007.txt > output_007.txt ./a.out < input_008.txt > output_008.txt ./a.out < input_009.txt > output_009.txt */ /* #include <bits/stdc++.h> using namespace std; const int N = 1e4 + 3; int n, m, deg[N]; vector<int> g[N], independent; bool vis[N], bad[N]; vector<vector<int>> comps; void dfs(int v){ if (v == 0) return; independent.push_back(v); vis[v] = 1; for (int u:g[v]){ bad[u] = 1; deg[u]--; } int mn_node = 0; for (int i=1; i<=n; i++){ if (!vis[i] && !bad[i] && deg[mn_node] > deg[i]){ mn_node = i; } } dfs(mn_node); } int main(){ cin >> n >> m; deg[0] = 1e9; for (int i=0; i<m; i++){ int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); deg[v]++; deg[u]++; } while(1){ int mn_node = 0; for (int i=1; i<=n; i++) if (!vis[i] && deg[mn_node] > deg[i]) mn_node = i; if (mn_node == 0) break; for (int i=1; i<=n; i++) bad[i] = 0; independent.clear(); dfs(mn_node); comps.push_back(independent); } cout << comps.size() << endl; for (auto x : comps){ for (auto v : x) cout << v << " "; cout << endl; } } */ #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int par1[N], par2[N], h[N], mnh[N]; bool vis[N]; vector<int> g[N]; vector<pair<int, int>> bridges; int root1(int v){ return (par1[v] == -1 ? v : par1[v] = root1(par1[v])); } int root2(int v){ return (par2[v] == -1 ? v : par2[v] = root2(par2[v])); } void merge1(int u, int v){ // cout << "merge1 : " << u << " " << v << endl; int r1 = root1(v); int r2 = root1(u); par1[r1] = r2; g[v].push_back(u); g[u].push_back(v); } void merge2(int u, int v){ int r1 = root2(u); int r2 = root2(v); if (r1 == r2) return; par2[r1] = r2; g[v].push_back(u); g[u].push_back(v); } void dfs(int v, int p = -1){ // cout << v << endl; vis[v] = 1; mnh[v] = h[v]; for (int u : g[v]){ // cout << v << " -- " << u << endl; if (vis[u]){ if (u != p) mnh[v] = min(mnh[v], h[u]); continue; } h[u] = h[v] + 1; dfs(u, v); mnh[v] = min(mnh[v], mnh[u]); // cout << u << " : " << mnh[u] << endl; if (mnh[u] >= h[u]) bridges.push_back({u, v}); } } int main(){ int n, m; scanf("%d %d", &n, &m); for (int i=1; i<=n; i++) par1[i] = par2[i] = -1; for (int i=0; i<m; i++){ int u, v; scanf("%d %d", &u, &v); if (root1(u) == root1(v)) merge2(u, v); else merge1(u, v); } for (int v = 1; v <= n; v++){ if (!vis[v]){ // cout << "---------------\n"; dfs(v); } } for (auto [u, v] : bridges) printf("%d %d\n", u, v); } /* #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int par1[N], par2[N], h[N], mnh[N]; bool vis[N]; vector<int> g[N]; vector<pair<int, int>> bridges; int root1(int v){ return (par1[v] == -1 ? v : par1[v] = root1(par1[v])); } int root2(int v){ return (par2[v] == -1 ? v : par2[v] = root2(par2[v])); } void merge1(int u, int v){ int r1 = root1(v); int r2 = root1(u); par1[r1] = r2; g[v].push_back(u); g[u].push_back(v); } void merge2(int u, int v){ int r1 = root2(u); int r2 = root2(v); if (r1 == r2) return; par2[r1] = r2; g[v].push_back(u); g[u].push_back(v); } void dfs(int v, int p = -1){ vis[v] = 1; mnh[v] = h[v]; for (int u : g[v]){ if (vis[u]){ if (u != p) mnh[v] = min(mnh[v], h[u]); continue; } h[u] = h[v] + 1; dfs(u, v); mnh[v] = min(mnh[v], mnh[u]); if (mnh[u] >= h[u]) bridges.push_back({u, v}); } } int main(){ int n, m; scanf("%d%d", &n, &m); for (int i=1; i<=n; i++) par1[i] = par2[i] = -1; for (int i=0; i<m; i++){ int u, v; scanf("%d%d", &u, &v); if (root1(u) == root1(v)) merge2(u, v); else merge1(u, v); } for (int v = 1; v <= n; v++) if (!vis[v]) dfs(v); for (auto [u, v] : bridges) printf("%d %d\n", u, v); } */

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

pipes.cpp: In function 'int main()':
pipes.cpp:224:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:231:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  231 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
#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...
#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...