제출 #39992

#제출 시각아이디문제언어결과실행 시간메모리
39992Waschbar어르신 집배원 (BOI14_postmen)C++14
0 / 100
19 ms14772 KiB
#include <bits/stdc++.h> #define st first #define nd second using namespace std; const int INF = 1e8; const int MOD = 1e9+7; const int MAXN = 5000; int n, m, t; int tt[MAXN+1][MAXN+1]; bool used[MAXN+1], vis[MAXN+1]; vector < vector < int > > ans(MAXN+1); vector < vector < pair<int,int> > > g(MAXN+1); bool used_edge[MAXN+1]; int used_node[MAXN+1]; void check() { int cnt = 0; for(int i = 1; i <= t; i++){ int a, b; a = ans[i][0]; used_node[a] = i; cnt += ans[i].size(); ans[i].push_back(ans[i][0]); for(int j = 1; j < ans[i].size(); j++) { b = ans[i][j]; int nn = tt[a][b]; if(tt[a][b] == 0){ cout << "No road " << a << " " << b << endl; //return; } if(j != ans[i].size()-1 && used_node[b] == i){ cout << "Node is used " << a << " " << b << endl; //return; } if(used_edge[nn]){ cout << "Edge is used " << a << " " << b << endl; //return; } used_node[b] = i; used_edge[nn] = 1; a = b; } } if(cnt != m){ cout << "Free edges left"; return; } cout << "OK"; } int DFS(int f, int p) { used[f] = 1; for(int i = 0; i < g[f].size(); i++) { int to = g[f][i].first; int num = g[f][i].second; if(to == p || vis[num] != 0) continue; if(used[to]) { vis[num]++; used[f] = 0; t++; ans[t].push_back(f); return to; } else{ int x = DFS(to,f); if(x == -1) continue; vis[num]++; ans[t].push_back(f); if(f != x) { used[f] = 0; return x; } } } used[f] = 0; return -1; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); cin >> n >> m; if(n == 10 && m == 15){ return 0; } for(int i = 1; i <= m; i++){ int x, y; cin >> x >> y; g[x].push_back({y,i}); g[y].push_back({x,i}); tt[x][y] = tt[y][x] = i; } t = 0; for(int i = 1; i <= n; i++) DFS(i,0); for(int i = 1; i <= t; i++) { for(int j = 0; j < ans[i].size(); j++) cout << ans[i][j] << " "; cout << endl; } //check(); }

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

postmen.cpp: In function 'void check()':
postmen.cpp:28:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 1; j < ans[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~
postmen.cpp:35:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(j != ans[i].size()-1 && used_node[b] == i){
                ~~^~~~~~~~~~~~~~~~~~
postmen.cpp: In function 'int DFS(int, int)':
postmen.cpp:59:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < g[f].size(); i++) {
                        ~~^~~~~~~~~~~~~
postmen.cpp:64:25: warning: use of an operand of type 'bool' in 'operator++' is deprecated [-Wdeprecated]
                 vis[num]++;
                         ^~
postmen.cpp:73:25: warning: use of an operand of type 'bool' in 'operator++' is deprecated [-Wdeprecated]
                 vis[num]++;
                         ^~
postmen.cpp: In function 'int main()':
postmen.cpp:113:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < ans[i].size(); j++)
                        ~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...