Submission #135922

#	Time	Username	Problem	Language	Result	Execution time	Memory
135922		Zex	Senior Postmen (BOI14_postmen)	C++11	0 / 100	8 ms	4236 KiB

postmen

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define INF INT_MAX
#define output for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { cout << adj[i][j] << " "; }cout<<endl; }cout<<endl;

const int maxN = 2001;
int N, M;
bool adj[maxN][maxN];
vector < vector<int> > res;
vector <int> path;
bool visited[maxN];
int root; bool foundCycle;

void dfs( int p, int x ){

    // cout << p << " -> " << x << endl;

    if( x == root ){ // cout << "FOUND ROOT" << endl;
        foundCycle = true;
        adj[x][p] = adj[p][x] = false;
        return;
    }
    if( visited[x] ) return;
    visited[x] = true;

    for(int j=1;j<=N;j++){ if( j == p || j == x ) continue; 

        if( !adj[x][j] ) continue;

        adj[x][j] = adj[j][x] = false;
        dfs( x, j );
        if( foundCycle ){
            // cout << "FOUND ROOT, DISABLE " << p << "->" << x << " AND " << x << "->" << j << endl;
            path.push_back(j); return;
        }
        adj[x][j] = adj[j][x] = true;

    }

}

void printVec( vector <int> v ){

    for(int i=0;i<v.size();i++) cout << v[i] << " ";
    cout << endl;

}

int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    memset( adj, 0, sizeof adj );

    cin >> N >> M;

    int x, y;
    for(int i=0;i<M;i++){
        cin >> x >> y;
        adj[x][y] = adj[y][x] = true;
    }

    for(int i=1;i<=N;i++) for(int j=1;j<=N;j++){

        if( !adj[i][j] ) continue;
        adj[i][j] = adj[j][i] = false;

        memset( visited, 0, sizeof visited );
        path.clear(); root = i; foundCycle = false;
        dfs( i, j );
        path.push_back( j ); path.push_back( i );
        if( path.size() == 2 ) continue;
        reverse( path.begin(), path.end() );
        // printVec( path );
        // output;
        res.push_back(path);

    }

    for(int i=0;i<res.size();i++){
        printVec( res[i] );
    }

}

Compilation message (stderr)

postmen.cpp: In function 'void printVec(std::vector<int>)':
postmen.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();i++) cout << v[i] << " ";
                 ~^~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<res.size();i++){
                 ~^~~~~~~~~~~

• Subtask 1: 0 / 38
• Subtask 2: 0 / 17
• Subtask 3: 0 / 45