oj.uz

Submission #161708

# Submission time Handle Problem Language Result Execution time Memory
161708 2019-11-03T20:28:36 Z sans Flood (IOI07_flood) C++14
20 / 100
 2000 ms 32528 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB Output isn't correct

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 339 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 346 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 6744 KB Output isn't correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 24208 KB Time limit exceeded

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 263 ms 24112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 28960 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2072 ms 32528 KB Time limit exceeded
2 Halted 0 ms 0 KB -