oj.uz

Submission #1031986

# Submission time Handle Problem Language Result Execution time Memory
1031986 2024-07-23T09:27:45 Z Neco_arc Flood (IOI07_flood) C++17
100 / 100
 83 ms 17316 KB 
#include <bits/stdc++.h>
#ifdef LOCAL
#include <bits/debug.hpp>
#endif // LOCAL

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "flood"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;
const vector<int> prio = {1, 0, 3, 2};


int n, m;
int d[maxn], del[maxn];
struct dl {
    pair<int, int> coord;
    int id;
} point[maxn];
int ID[maxn];
vector<pair<int, int>> edges[maxn];

void create_edge(int i, int j, int id) {
    int x, y, u, v;
    tie(x, y) = point[i].coord, tie(u, v) = point[j].coord;
    pair<int, int> val = {j, id};

    if(x == u) {
        if(v > y) edges[i][0] = val;
        else edges[i][2] = val;
    }

    if(y == v) {
        if(u > x) edges[i][3] = val;
        else edges[i][1] = val;
    }
}

bool check(int u) {
    for(auto [v, id] : edges[u]) if(!del[id]) return 1;
    return 0;
}

void dfs(int u)
{
    int rt = u, dir = 0;
    vector<int> visited_edges;

    do {
        pair<int, int> v;
        for(int t : prio) {
            v = edges[u][(dir + t) % 4];
            if(!del[v.second]) {
                dir = (dir + t) % 4;
                break;
            }
        }

//        cout << u << " " << v.first << " " << dir << '\n';

        visited_edges.push_back(v.second);
        u = v.first;

    } while(u != rt);

    for(int x : visited_edges) d[x] ++, del[x] = 1;
}

void solve()
{
    cin >> n;
    fi(i, 1, n) {
        cin >> point[i].coord.first >> point[i].coord.second;
        point[i].id = i;
        edges[i].resize(4);
    }

    sort(point + 1, point + 1 + n, [](dl x, dl y) {
            return x.coord < y.coord;
        });

    fi(i, 1, n) ID[point[i].id] = i;

    cin >> m;
    fi(i, 1, m) {
        int x, y; cin >> x >> y;

        x = ID[x], y = ID[y];
        create_edge(x, y, i);
        create_edge(y, x, i);
    }

    del[0] = 1;
    fi(i, 1, n) {
        while(check(i)) dfs(i);
    }

    vector<int> ans;
    fi(i, 1, m) if(d[i] == 2) ans.push_back(i);

    cout << ans.size() << '\n';
    for(int x : ans) cout << x << '\n';

}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
flood.cpp:127:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 4 ms 7520 KB Output is correct
3 Correct 3 ms 7512 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 4 ms 7512 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7512 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9564 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 14892 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 14928 KB Output is correct
2 Correct 59 ms 17100 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 16596 KB Output is correct
2 Correct 83 ms 17316 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 17140 KB Output is correct
2 Correct 59 ms 17144 KB Output is correct