oj.uz

Submission #39992

# Submission time Handle Problem Language Result Execution time Memory
39992 2018-01-25T06:57:36 Z Waschbar Senior Postmen (BOI14_postmen) C++14
0 / 100
 19 ms 14772 KB 
#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();

}

Compilation message

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++)
                        ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 17 ms 14772 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 8 ms 1152 KB Output is correct
7 Incorrect 13 ms 2048 KB Edge does not exist or used 3, 1
8 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 14 ms 14720 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 8 ms 1152 KB Output is correct
7 Incorrect 10 ms 2048 KB Edge does not exist or used 3, 1
8 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 6 ms 616 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 19 ms 14720 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct
7 Incorrect 10 ms 2048 KB Edge does not exist or used 3, 1
8 Halted 0 ms 0 KB -