Submission #161708

#	Time	Username	Problem	Language	Result	Execution time	Memory
161708		sans	Flood (IOI07_flood)	C++14	20 / 100	2072 ms	32528 KiB

flood

#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>

using namespace std;

#define sp ' '
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define forn(YY, yy) for(int yy = 0; yy < YY; ++yy)

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> ii;

int N, W;
vector<ii> cor;
vector<pair<ii, int>> corSorted;

vvi AdjList;
map<ii, int> walls;
map<int, bool> saglam;

//Input
void input(void)
{
    cin >> N; AdjList.resize(N);
    for(int i = 0; i < N; ++i)
    {
        int x, y;
        cin >> x >> y;
        cor.pb(mp(x, y));
        corSorted.pb(mp(mp(x, y), i));
    }
    sort(corSorted.begin(), corSorted.end());
    cin >> W;
    for(int i = 0; i < W; ++i)
    {
        int u, v; cin >> u >> v; u--; v--;
        walls[mp(u, v)] = walls[mp(v, u)] = i;
        saglam[i] = true;
        AdjList[u].pb(v);
        AdjList[v].pb(u);
    }
}

vector<bool> visited;
int startNode;
stack<int> nodes;

void duvaryik(stack<int> &s)
{
    while(!s.empty())
    {
        int top1 = s.top(); s.pop();
        if(!s.empty())
        {
            int top2 = s.top();
            saglam[walls[mp(top1, top2)]] = false;
        }
    }
    return;
}

bool compare(const pair<ii, int> &p1, const pair<ii, int> &p2)
{
    if(p1.st.st > p2.st.st and p1.st.nd > p2.st.nd) return true;
    if(p2.st.st > p1.st.st and p2.st.nd > p1.st.nd) return false;

    if(p1.st.st < p2.st.st and p1.st.nd < p2.st.nd) return true;
    if(p2.st.st < p1.st.st and p2.st.nd < p1.st.nd) return false;

    if(p1.st.st < p2.st.st and p1.st.nd > p2.st.nd) return true;
    if(p2.st.st < p1.st.st and p2.st.nd > p1.st.nd) return false;

    if(p1.st.st < p2.st.st and p1.st.nd > p2.st.nd) return true;
    if(p2.st.st < p1.st.st and p2.st.nd > p1.st.nd) return false;

    return true;
}

bool bitti = false;
void traverse(int n, int b)
{
    visited[n] = true;
    if(n == startNode and b != 0){ duvaryik(nodes); visited[n] = false; bitti = true; return; }

    vector<pair<ii, int>> VN;
    for(int i = 0; i < (int)AdjList[n].size(); ++i)
        if(saglam[walls[mp(n, AdjList[n][i])]] and (!visited[AdjList[n][i]] or (AdjList[n][i] == startNode and b > 2)))
            VN.pb(mp(cor[AdjList[n][i]], AdjList[n][i]));

    sort(VN.begin(), VN.end(), compare);
    for(int i = 0; i < (int)VN.size(); ++i)
    {
        nodes.push(VN[i].nd);
        traverse(VN[i].nd, b+1);
        if(bitti){ visited[n] = false; return; }
        nodes.pop();
    }
    visited[n] = false;
    return;
}

int main(int argc, char **argv)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();

    visited.assign(N, false);

    for(int i = 0; i < corSorted.size(); ++i)
    {
        bitti = false;
        startNode = corSorted[i].nd;
        nodes.push(startNode);
        traverse(startNode, 0);
    }

    int sum = 0; vi ans;
    for(auto itr = saglam.begin(); itr != saglam.end(); ++itr)
        if(itr->nd){ ans.pb((itr->st)+1); sum++; }

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

    return 0;
}

//cikisir

Compilation message (stderr)

flood.cpp: In function 'int main(int, char**)':
flood.cpp:119:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < corSorted.size(); ++i)
                    ~~^~~~~~~~~~~~~~~~~~
flood.cpp:132:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size(); ++i) cout << ans[i] << endl;
                    ~~^~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 3
• Subtask 5: 0 / 10
• Subtask 6: 0 / 3
• Subtask 7: 0 / 3
• Subtask 8: 0 / 3
• Subtask 9: 0 / 3
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9
• Subtask 12: 0 / 9
• Subtask 13: 0 / 9
• Subtask 14: 0 / 9