제출 #1337140

#제출 시각아이디문제언어결과실행 시간메모리
1337140khanhphucscratchFlood (IOI07_flood)C++20
73 / 100
248 ms43124 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Point
{
    int x, y;
    Point(int x, int y): x(x), y(y){}
    Point operator -(Point &p)
    {
        return Point(x-p.x, y-p.y);
    }
    int cross(Point &p)
    {
        return x*p.y - y*p.x;
    }
    int half()
    {
        if(y > 0 || (y == 0 && x > 0)) return 0;
        else return 1;
    }
};
vector<Point> p;
vector<vector<int>> ad, used;
vector<vector<int>> find_all_faces(int n)
{
    for(int i = 1; i <= n; i++){
        used[i].resize(ad[i].size());
        sort(ad[i].begin(), ad[i].end(), [&](const int x, const int y){
            Point px = p[x] - p[i], py = p[y] - p[i];
            if(px.half() != py.half()) return px.half() < py.half();
            else return px.cross(py) > 0;
        });
    }
    vector<vector<int>> ans;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < ad[i].size(); j++) if(used[i][j] == 0){
            int u = i, e = j, sum = 0;
            vector<int> cur;
            while(used[u][e] == 0){
                cur.push_back(u);
                used[u][e] = 1;
                int v = ad[u][e];
                e = lower_bound(ad[v].begin(), ad[v].end(), u, [&](const int x, const int y){
                    Point px = p[x] - p[v], py = p[y] - p[v];
                    if(px.half() != py.half()) return px.half() < py.half();
                    else return px.cross(py) > 0;
                }) - ad[v].begin() + 1;
                if(e == ad[v].size()) e = 0;
                sum += p[u].cross(p[v]);
                u = v;
            }
            if(sum < 0) ans.push_back(cur);
        }
    }
    return ans;
}
vector<int> adbfs[200005], in_face[200005];
int dis[200005];
map<pair<int, int>, int> f;
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n;
    p.emplace_back(0, 0);
    for(int i = 1; i <= n; i++){
        int x, y; cin>>x>>y;
        p.emplace_back(x, y);
    }
    ad.resize(n+5); used.resize(n+5);
    int m; cin>>m;
    for(int i = 1; i <= m; i++){
        int u, v; cin>>u>>v;
        if(u > v) swap(u, v);
        f[{u, v}] = i;
        ad[u].push_back(v);
        ad[v].push_back(u);
    }
    vector<vector<int>> faces = find_all_faces(n);
    /*for(auto &i : faces){
        cerr<<"A"<<endl;
        for(int j : i) cerr<<j<<" ("<<p[j].x<<", "<<p[j].y<<")"<<endl;
        cerr<<endl;
    }*/
    for(int i = 0; i < faces.size(); i++){
        vector<int> &cur = faces[i];
        for(int j = 0; j < cur.size(); j++){
            int u = cur[j], v = cur[(j+1)%cur.size()];
            if(u > v) swap(u, v);
            in_face[f[{u, v}]].push_back(i+1);
        }
    }
    for(int i = 1; i <= m; i++) while(in_face[i].size() < 2) in_face[i].push_back(0);
    for(int i = 1; i <= m; i++){
        int u = in_face[i][0], v = in_face[i][1];
        //cerr<<"A"<<u<<" "<<v<<endl;
        adbfs[u].push_back(v);
        adbfs[v].push_back(u);
    }
    memset(dis, 0x3f, sizeof(dis));
    dis[0] = 0; queue<int> w; w.push(0);
    while(w.size() > 0){
        int u = w.front(); w.pop();
        for(int v : adbfs[u]) if(dis[v] > dis[u] + 1){
            dis[v] = dis[u] + 1;
            w.push(v);
        }
    }
    vector<int> ans;
    for(int i = 1; i <= m; i++){
        int u = in_face[i][0], v = in_face[i][1];
        if(dis[u] == dis[v]) ans.push_back(i);
    }
    cout<<ans.size()<<'\n';
    for(int i : ans) cout<<i<<'\n';
}

#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...