제출 #1339089

#제출 시각아이디문제언어결과실행 시간메모리
1339089vjudge1Flood (IOI07_flood)C++20
55 / 100
97 ms5072 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pii pair<ll,ll>
#define F first
#define S second
#define LOO(i,a,b) for (ll i = a; i<=b; i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define OOL(i,a,b) for (ll i = b; i >=a; i--)
void solve() {
    int n;
    cin>>n;
    vector<pii> points(n);
    vector<int> xs(n),ys(n);
    LOO(i,0,n-1) {
        cin>>points[i].F>>points[i].S;
        points[i].F+=2;
        points[i].S+=2;
        xs[i]=points[i].F;
        ys[i]=points[i].S;
    }
    sort(all(xs));
    sort(all(ys));
    LOO(i,0,n-1) {
        points[i].F=lower_bound(all(xs),points[i].F)-xs.begin()+2;
        points[i].S=lower_bound(all(ys),points[i].S)-ys.begin()+2;
    }
    vector wallright(510,vector(510, false));
    vector wallup(510, vector(510,false));
    vector wallleft=wallright;
    vector walldown=wallup;
    int w;
    cin>>w;
    vector<pii> droites(w);
    LOO(i,0,w-1) {
        int a,b;
        cin>>a>>b;
        a--;b--;
        droites[i]={a,b};
        if (points[a].F==points[b].F) {
            LOO(j,min(points[a].S,points[b].S),max(points[a].S,points[b].S)-1) {
                if (points[a].F) wallright[points[a].F-1][j]=true;
                wallleft[points[a].F][j]=true;
            }
        }
        else {
            LOO(j,min(points[a].F,points[b].F),max(points[a].F,points[b].F)-1) {
                walldown[j][points[a].S]=true;
                if (points[a].S) wallup[j][points[a].S-1]=true;
            }
        }
    }
    vector visited(510,vector<int>(510,-1));
    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<>> cool;
    cool.push({0,{0,0}});
    while (!cool.empty()) {
        auto top =cool.top();
        cool.pop();
   //     assert(top.S.F>=0 && top.S.S>=0 && top.S.F<510 && top.S.S<510);
        if (visited[top.S.F][top.S.S]!=-1) continue;
        visited[top.S.F][top.S.S]=top.F;
        if (top.S.F+1<510) cool.emplace(wallright[top.S.F][top.S.S]+top.F, make_pair(top.S.F+1,top.S.S));
        if (top.S.F-1>=0) cool.emplace(wallleft[top.S.F][top.S.S]+top.F, make_pair(top.S.F-1,top.S.S));
        if (top.S.S+1<510 ) cool.emplace(wallup[top.S.F][top.S.S]+top.F, make_pair(top.S.F,top.S.S+1));
        if (top.S.S>=1 ) cool.emplace(walldown[top.S.F][top.S.S]+top.F, make_pair(top.S.F,top.S.S-1));
    }
  //  OOL(j,0,30) {
  //      LOO(i,0,30) cout << visited[i][j] << ' ';
  //      cout << '\n';
  //  }
  //  cout << "dud" << endl;
    vector<int> mhm;
    LOO(i,0,w-1) {
        int x1 = points[droites[i].F].F;
        int x2 = points[droites[i].S].F;
        int y1 = points[droites[i].F].S;
        int y2 = points[droites[i].S].S;
        if (x1==x2) {
            y1=min(y1,y2);
            if (visited[x1][y1]==visited[x1-1][y1]) {
                mhm.push_back(i);
            }
        }
        else {
            x1=min(x1,x2);
            if (visited[x1][y1]==visited[x1][y1-1]) mhm.push_back(i);
        }
    }
    cout << mhm.size() << '\n';
    for (int ele: mhm) cout << ele+1 << '\n';

}
signed main() {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    while (t--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...