oj.uz

Submission #234977

# Submission time Handle Problem Language Result Execution time Memory
234977 2020-05-26T13:26:37 Z nicolaalexandra Flood (IOI07_flood) C++14
100 / 100
 558 ms 26732 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][2].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));
    }

    while (!s.empty()){

        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 && f[L[poz][2].second][0] == 0 && f[L[poz][2].second][1] == 0){
            y = L[poz][2].first;
            tip = 0, c = 1;
        } else {
            if (L[poz][1].first && f[L[poz][1].second][0] == 0 && f[L[poz][1].second][1] == 0){
                x = L[poz][1].first;
                tip = 1, c = 2;
            } else continue;
        }

        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:183:28: warning: right operand of comma operator has no effect [-Wunused-value]
         x = xx, y = yy, tip;
                            ^
flood.cpp:177:13: warning: unused variable 'idx' [-Wunused-variable]
         int idx = (*s.begin()).second;
             ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
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
3 Correct 5 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 288 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
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 5240 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 18116 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 19576 KB Output is correct
2 Correct 558 ms 25940 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 450 ms 23676 KB Output is correct
2 Correct 522 ms 26732 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 25720 KB Output is correct
2 Correct 387 ms 22768 KB Output is correct