10765 - Doves and bombs

[christephan]

My O(n^2) algorithm (DFS+heap) got TLE.

Any better solutions? THX.

[christephan]

I think I was sleepy..

When I get up today, I add backtracking to my DFS algorithm such that I can prevent re-calculating as much as posibble.
The algorithm now may be O(|E| + |V| log |V|), I'm not sure. (n log n is for heap sort), where |E| <= 10 |V|.

Then now AC with 0.03s

[ngchumin]

Hi, i keeping getting WA even though i tried on my inputs i devised myself. Any one able to help with any input cases?

Thanks alot!

[nbacool2]

OK, I make a standard implementation of finding the articulation points with a DFS. Got correct output on the sample test cases and other I made up myseld but I still get WA. Any ideas?

Code: Select all

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <utility>
using namespace std;
struct Station
{
    int number, pigeonValue;
    Station(int n = 0, int p = 0)
    {
        number = n;
        pigeonValue = p;
    }
    bool operator < (const Station &other) const
    {
        if(pigeonValue == other.pigeonValue) return number < other.number;
        return pigeonValue > other.pigeonValue;
    }
};
const int MAXN = 10001;
int N, M;
vector<int> G[MAXN];
int parent[MAXN];
bool visited[MAXN];
int DFSRoot;
int rootChildren;
bool articulationPoint[MAXN];
int pigeonValue[MAXN];
int numberOfTreeChildren[MAXN];
int dfs_num[MAXN];
int dfs_low[MAXN];
int counter;
vector<vector<Station> > answers;
int DFS(int root)
{
    visited[root] = true;
    dfs_num[root] = counter;
    dfs_low[root] = counter;
    ++counter;
    int nodes = 0;
    int SCCs = 0;
    for(int i = 0; i < G[root].size(); ++i)
    {
        int child = G[root][i];
        if(!visited[child])
        {
            ++numberOfTreeChildren[root];
            if(root == DFSRoot) ++rootChildren;
            parent[child] = root;
            nodes += DFS(child);
            if(dfs_low[child] >= dfs_num[root])
            {
                //cout<<root<<" is critical. Adding "<<child<<" as a root of a parent SCC\n";
                articulationPoint[root] = true;
                ++SCCs;
            }
            dfs_low[root] = min(dfs_low[root], dfs_low[child]);
        }
        else if(child != parent[root])
        {
            dfs_low[root] = min(dfs_low[root], dfs_num[child]);
        }
    }
    if(articulationPoint[root])
    {
        if(root != DFSRoot) ++SCCs;
        pigeonValue[root] = SCCs;
    }
    return nodes + 1;
}
void read()
{
    for(int i = 0; i < MAXN; ++i) G[i].clear();
    memset(parent, -1, sizeof parent);
    memset(visited, 0, sizeof visited);
    memset(articulationPoint, 0, sizeof articulationPoint);
    memset(pigeonValue, 0, sizeof pigeonValue);
    memset(numberOfTreeChildren, 0, sizeof numberOfTreeChildren);
    counter = 0;
    //now do shit
    while(true)
    {
        int from, to;
        cin >> from >> to;
        if(from == -1 && to == -1) break;
        G[from].push_back(to);
        G[to].push_back(from);
    }
    for(int i = 0; i < N; ++i)
    {
        if(!visited[i])
        {
            DFSRoot = i;
            rootChildren = 0;
            int nodeCount = DFS(i);
            if(rootChildren > 1)
            {
                articulationPoint[i] = true;
                pigeonValue[i] = numberOfTreeChildren[i];
            }
        }
    }
    //cout<<"Articulation points are:\n";
    vector<Station> stations;
    for(int i = 0; i < N; ++i)
    {
        if(articulationPoint[i])
        {
            stations.push_back(Station(i, pigeonValue[i]));
            //cout<<i<<" "<<pigeonValue[i]<<endl;
        }
    }
    //cout<<"END";
    sort(stations.begin(), stations.end());
    stations.resize(M);
    answers.push_back(stations);
}
int main()
{
    ios::sync_with_stdio(false);
    while(true)
    {
        cin >> N >> M;
        if(N == 0 && M == 0) break;
        read();
    }
    //cout<<"RESULT:\n";
    for(int i = 0; i < answers.size(); ++i)
    {
        for(int j = 0; j < answers[i].size(); ++j)
        {
            cout<<answers[i][j].number<<" "<<answers[i][j].pigeonValue<<'\n';
        }
        if(i < answers.size()-1)cout<<'\n';
    }
    return 0;
}

[brianfry713]

Print a blank line after the output for each set of input, including the last one.

[nbacool2]

With and without printing the additional blank line afer the last test case I still get WA :/

[brianfry713]

Post your updated code.

[just_yousef]

Never mind I found the bug