oj.uz

Submission #234960

# Submission time Handle Problem Language Result Execution time Memory
234960 2020-05-26T12:48:00 Z nicolaalexandra Flood (IOI07_flood) C++14
33 / 100
 2000 ms 65540 KB 
#include <bits/stdc++.h>
#define DIM 200010
using namespace std;

pair <int,int> v[DIM],L[DIM][5],z[DIM];
map <pair<int,int>,int> pos;
set <pair<pair<int,int>,int> > s;
vector <int> sol,w;
int f[DIM][2];
int n,m,i,j,x,y,tip,poz,dir,c,poz1,poz2,x2,y2;


void solve_vert (){
    /// nu stiu cum s au facut atatea cazuri
    if (c == 1){

        if (dir == 0 && L[poz][3].second){
            x = L[poz][3].first, tip = 1, c = 1;
            return;
        }
        if (dir == 1 && L[poz][1].second){
            x = L[poz][1].first, tip = 1, c = 2, dir = 0;
            return;
        }
        ///////////////
        if (L[poz][2].second){
            y = L[poz][2].first, c = 1;
            return;
        }
        ////////
        if (dir == 0 && L[poz][1].second){
            x = L[poz][1].first, tip = 1, c = 2, dir = 1;
            return;
        }
        if (dir == 1 && L[poz][3].second){
            x = L[poz][3].first, tip = 1, c = 1, dir = 1;
            return;
        }
        ////////
        if (L[poz][0].second){
            y = L[poz][0].first, dir = 1-dir, c = 2;
            return;
        }

    } else {
        if (dir == 0 && L[poz][3].second){
            x = L[poz][3].first, tip = 1, dir = 1, c = 1;
            return;
        }
        if (dir == 1 && L[poz][1].second){
            x = L[poz][1].first, tip = 1, dir = 1, c = 2;
            return;
        }
        ///////
        if (L[poz][0].second){
            y = L[poz][0].first;
            return;
        }
        //////
        if (dir == 0 && L[poz][1].second){
            x = L[poz][1].first, tip = 1, dir = 0, c = 2;
            return;
        }
        if (dir == 1 && L[poz][3].second){
            x = L[poz][3].first, tip = 1, dir = 0, c = 1;
            return;
        }

        ////
        if (L[poz][2].second){
            y = L[poz][2].first, c = 1, dir = 1 - dir;
            return;
        }
    }
}
void solve_oriz (){
    if (c == 1){
        if (dir == 0 && L[poz][0].second){
            y = L[poz][0].first, tip = 0, c = 2, dir = 1;
            return;
        }
        if (dir == 1 && L[poz][2].second){
            y = L[poz][0].first, tip = 0, c = 1, dir = 1;
            return;
        }
        //////
        if (L[poz][3].second){
            x = L[poz][3].first;
            return;
        }
        //////
        if (dir == 0 && L[poz][2].second){
            y = L[poz][2].first, tip = 0, c = 1, dir = 0;
            return;
        }
        if (dir == 1 && L[poz][0].second){
            y = L[poz][0].first, tip = 0, c = 2, dir = 0;
            return;
        }
        ////
        if (L[poz][1].second){
            x = L[poz][1].first, dir = 1 - dir, c = 2;
            return;
        }

    } else {

        if (dir == 0 && L[poz][0].second){
            y = L[poz][0].first, tip = 0, dir = 0, c = 2;
            return;
        }
        if (dir == 1 && L[poz][2].second){
            y = L[poz][2].first, tip = 0, dir = 0, c = 1;
            return;
        }
        ///////
        if (L[poz][1].second){
            x = L[poz][1].first;
            return;
        }
        //////
        if (dir == 0 && L[poz][2].second){
            y = L[poz][2].first, tip = 0, dir = 1, c = 1;
            return;
        }
        if (dir == 1 && L[poz][0].second){
            y = L[poz][0].first, tip = 0, dir = 1, c = 2;
            return;
        }
        /////
        if (L[poz][3].second){
            x = L[poz][3].first, dir = 1-dir, c = 1;
            return;
        }

    }


}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>v[i].first>>v[i].second;
        pos[v[i]] = i;
    }

    cin>>m;
    for (i=1;i<=m;i++){
        cin>>poz1>>poz2;
        if (v[poz1].first > v[poz2].first || v[poz1].second > v[poz2].second)
            swap (poz1,poz2);

        z[i] = make_pair(poz1,poz2);
        x = v[poz1].first, y = v[poz1].second;
        x2 = v[poz2].first, y2 = v[poz2].second;

        if (x == x2){ /// zid vertical
            L[poz1][0] = make_pair (y2,i);
            L[poz2][2] = make_pair (y,i);
        } else { /// zid orizontal
            L[poz1][1] = make_pair (x2,i);
            L[poz2][3] = make_pair (x,i);
        }

        /// pun cate un punct pt fiecare zid
        s.insert (make_pair(make_pair(-y2,x),i));
    }

    for (;;){
        if (s.empty())
            break;
        int xx = (*s.begin()).first.second;
        int yy = -(*s.begin()).first.first;
        int idx = (*s.begin()).second;

        s.erase(s.begin());
        if (f[idx][0] || f[idx][1])
            continue;

        x = xx, y = yy, tip;

        /// vad daca am vreun zid vertical
        poz = pos[make_pair(x,y)];

        if (L[poz][2].second){
            y = L[poz][2].first;
            tip = 0, c = 1;
        } else {
            x = L[poz][1].first;
            tip = 1, c = 2;
        }

        dir = 0; /// de care parte a zidului ma aflu

        w.clear();
        /// marchez zidul pe care ma aflu
        if (tip == 0){
            if (c == 1)
                f[L[poz][2].second][dir] = 1, w.push_back(L[poz][2].second);
            else f[L[poz][0].second][dir] = 1, w.push_back(L[poz][0].second);
        } else {
            if (c == 1)
                f[L[poz][3].second][dir] = 1, w.push_back(L[poz][3].second);

            else f[L[poz][1].second][dir] = 1, w.push_back(L[poz][1].second);
        }

        //cout<<x<<" "<<y<<"\n";
        while (!(x == xx && y == yy)){

            poz = pos[make_pair(x,y)];

            if (tip == 0) /// vert
                solve_vert ();
            else solve_oriz();

            //cout<<x<<" "<<y<<"\n";

            /// marchez zidul pe care sunt acum
            poz = pos[make_pair(x,y)];
            if (tip == 0){
                if (c == 1)
                    f[L[poz][0].second][dir] = 1, w.push_back(L[poz][0].second);
                else f[L[poz][2].second][dir] = 1, w.push_back(L[poz][2].second);
            } else {
                if (c == 1)
                    f[L[poz][1].second][dir] = 1, w.push_back(L[poz][1].second);
                else f[L[poz][3].second][dir] = 1, w.push_back(L[poz][3].second);
            }

        }
        //cout<<"\n";
        /// acum trb sa sterg zidurile
        for (auto it : w){
            int poz1 = z[it].first, poz2 = z[it].second;
            x = v[poz1].first, y = v[poz1].second;
            x2 = v[poz2].first, y2 = v[poz2].second;

            if (x == x2){ /// zid vertical
                L[poz1][0] = make_pair (0,0);
                L[poz2][2] = make_pair (0,0);
            } else { /// zid orizontal
                L[poz1][1] = make_pair (0,0);
                L[poz2][3] = make_pair (0,0);
            }
        }

    }
    for (i=1;i<=m;i++)
        if (f[i][0] && f[i][1])
            sol.push_back(i);
    cout<<sol.size()<<"\n";
    for (auto it : sol)
        cout<<it<<"\n";

    return 0;
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:184:28: warning: right operand of comma operator has no effect [-Wunused-value]
         x = xx, y = yy, tip;
                            ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 416 KB Output is correct
3 Incorrect 5 ms 384 KB Output isn't correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #4
0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #7
0 / 3.0

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

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 386 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 377 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 693 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #11
0 / 9.0

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

Subtask #12
0 / 9.0

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

Subtask #13
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 1036 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 906 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -