oj.uz

Submission #54397

# Submission time Handle Problem Language Result Execution time Memory
54397 2018-07-03T10:08:21 Z 강태규(#1471) Flood (IOI07_flood) C++11
100 / 100
 462 ms 32392 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int inf = 1e7;
const int MAXX = 1e6;
int n, w;
int x[100001];
int y[100001];
int as[200001];
int bs[200001];
int wall[100001][4];

struct point {
    int x, y, up, dn;
    bool operator<(const point &p) const {
        if (x == p.x) return up < p.up;
        return x < p.x;
    }
} ps[400001];
vector<int> edge[400040];
bool visited[400040];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", x + i, y + i);
    }
    scanf("%d", &w);
    for(int i = 1; i <= w; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        as[i] = a; bs[i] = b;
        if (x[a] == x[b]) {
            if (y[a] > y[b]) swap(a, b);
            wall[a][1] = wall[b][3] = i;
            edge[a << 2 | 1].push_back((b << 2 | 3) << 1 | 1);
            edge[b << 2 | 3].push_back((a << 2 | 1) << 1 | 1);
        }
        else {
            if (x[a] > x[b]) swap(a, b);
            wall[a][0] = wall[b][2] = i;
            edge[a << 2 | 0].push_back((b << 2 | 2) << 1 | 1);
            edge[b << 2 | 2].push_back((a << 2 | 0) << 1 | 1);
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (wall[i][j]) {
                for (int c = (j + 1) & 3; ; c = (c + 1) & 3) {
                    if (wall[i][c]) {
                        int x = wall[i][c];
                        int a = as[x], b = bs[x];
                        int i2 = a ^ b ^ i, j2 = c ^ 2;
                        int x1 = i << 2 | j, x2 = i2 << 2 | j2;
                        edge[x1].push_back(x2 << 1);
                        edge[x2].push_back(x1 << 1);
                        break;
                    }
                }
            }
        }
    }
    
    int m = 0;
    for (int i = 1; i <= w; ++i) {
        int a = as[i], b = bs[i];
        if (x[a] == x[b]) continue;
        if (x[a] > x[b]) swap(a, b);
        int up = b << 2 | 2;
        int dn = a << 2 | 0;
        ps[m++] = { x[a], y[a], up, dn };
        ps[m++] = { x[b], y[a], -1, 0 };
    }
    
    sort(ps, ps + m);
    int * ch = (int *)visited;
    int tp = 0;
    map<int, pii> mp;
    mp[-1] = mp[MAXX + 1] = pii(0, 0);
    map<int, pii>::iterator it1, it2;
    for (int i = 0, j = ps[0].x; i <= m; ++i) {
        if (j < ps[i].x) {
            for (int p = 0; p < tp; ++p) {
                int x = ch[p];
                it1 = mp.lower_bound(x);
                it2 = it1--;
                int a = it1->second.second;
                int b = it2->second.first;
                edge[a].push_back(b << 1);
                edge[b].push_back(a << 1);
            }
            tp = 0;
            j = ps[i].x;
        }
        if (i == m) break;
        ch[tp++] = ps[i].y;
        ch[tp++] = ps[i].y + 1;
        if (ps[i].up < 0) mp.erase(ps[i].y);
        else mp[ps[i].y] = pii(ps[i].up, ps[i].dn);
    }
    
    int * dist = (int *)ps;
    dist[0] = 0;
    visited[0] = 0;
    for (int i = 1; i <= (n << 2 | 3); ++i) dist[i] = inf, visited[i] = 0;
    
    deque<int> q;
    q.push_back(0);
    while (!q.empty()) {
        int x = q.front();
        q.pop_front();
        if (visited[x]) continue;
        visited[x] = 1;
        for (int i : edge[x]) {
            int j = i >> 1;
            int d = dist[x] + (i & 1);
            if (d < dist[j]) {
                dist[j] = d;
                if (i & 1) q.push_back(j);
                else q.push_front(j);
            }
        }
    }
    vector<int> ans;
    for(int i = 1; i <= w; ++i) {
        int a = as[i], b = bs[i];
        if (x[a] == x[b]) {
            if (y[a] > y[b]) swap(a, b);
            if (dist[a << 2 | 1] == dist[b << 2 | 3]) ans.push_back(i);
        }
        else {
            if (x[a] > x[b]) swap(a, b);
            if (dist[a << 2 | 0] == dist[b << 2 | 2]) ans.push_back(i);
        }
    }
    
    printf("%d\n", (int)ans.size());
    for (int i : ans) printf("%d\n", i);
    
	return 0;
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
flood.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", x + i, y + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
flood.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &w);
     ~~~~~^~~~~~~~~~
flood.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9720 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9976 KB Output is correct

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9976 KB Output is correct
2 Correct 10 ms 10060 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10060 KB Output is correct
2 Correct 10 ms 10060 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 10060 KB Output is correct

Subtask #7
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10060 KB Output is correct

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10080 KB Output is correct
2 Correct 10 ms 10080 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10080 KB Output is correct
2 Correct 10 ms 10080 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 13600 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 23032 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 25212 KB Output is correct
2 Correct 457 ms 31084 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 31084 KB Output is correct
2 Correct 462 ms 32392 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 32392 KB Output is correct
2 Correct 306 ms 32392 KB Output is correct