제출 #349926

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
349926		Sara	Flood (IOI07_flood)	C++14	100 / 100	339 ms	31456 KiB

flood

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll unsigned long long
#define F first
#define S second
#define pb push_back
#define pf push_front
 
const ll N = 1e5 + 2;
const ll LOG = 20;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 5;
 
int n, W;
struct Point{
    int x, y;
} p[N];

vector < pair <int, bool> > g[4 * N];
int in[4][N];
vector < pair <int, int> > nodes;
int h[4 * N];
int ans;
 
inline void add_edge(int u, int v, bool w){
    g[u].pb({v, w}); g[v].pb({u, w});
    return;
}
 
inline void scan(){
    cin >> n;
    for (int i = 1; i <= n; i ++){
        cin >> p[i].x >> p[i].y;
        for (int j : {0, 1, 2, 3}){
            in[j][i] = -1;
        }
    }
    cin >> W;
    for (int i = 1; i <= W; i ++){
        int a, b;
        cin >> a >> b;
        if (p[a].x == p[b].x){
            if (p[b].y < p[a].y) swap(a, b);
            in[2][a] = i; in[0][b] = i;
        }
        else {
            if (p[b].x < p[a].x) swap(a, b);
            in[1][a] = i; in[3][b] = i;
            nodes.pb({p[a].y, 2 * i + 1});
        }
        int u = 2 * i; int v = u + 1;
        add_edge(u, v, 1);
    }
    sort(nodes.begin(), nodes.end());
    return;
}
 
inline void add_edges(){
    for (int i = 1; i <= n; i ++){
        for (int j : {0, 1, 2, 3}){
            if (in[j][i] == -1) continue;
            int k = (j + 1) % 4;
            while (in[k][i] == -1) k = (k + 1) % 4;
            int u = 2 * in[j][i] + (j == 0 || j == 3);
            int v = 2 * in[k][i] + (k == 1 || k == 2);
            add_edge(u, v, 0);  
        }
    }
    return;
}
 
deque <int> d;
inline void bfs(int root){
    d.pb(root); 
    h[root] = 0;
    while (d.size()){
        int v = d.back();
        d.pop_back();
        for (auto i : g[v]){
            int u = i.F, w = i.S;
            if (h[v] + w < h[u]){
                h[u] = h[v] + w;
                if (w) d.pf(u);
                else   d.pb(u);
            }
        }
    }
    return;
}
 
inline void print(){
    for (int i = 1; i <= W; i ++){
        if (h[2 * i] == h[2 * i + 1]){
            ans ++;
        }
    }
    cout << ans << '\n';
    for (int i = 1; i <= W; i ++){
        if (h[2 * i] == h[2 * i + 1]){
            cout << i << '\n';
        }
    }
    return;
}
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    scan();
    add_edges();
    fill(h, h + 4 * N, INF);
    for (auto i : nodes){
        if (h[i.S] == INF){
            bfs(i.S);
        }
    }
    print();
    return 0;
}         

• 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