제출 #234977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234977		nicolaalexandra	Flood (IOI07_flood)	C++14	100 / 100	558 ms	26732 KiB

flood

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9