답안 #54393 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54393	2018-07-03T09:59:46 Z	강태규(#1471)	Flood (IOI07_flood)	C++11	82 / 100	525 ms	33792 KB

flood

#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];
int dist[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);
    vector<int> ch;
    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 x : ch) {
                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);
            }
            ch.clear();
            j = ps[i].x;
        }
        if (i == m) break;
        ch.push_back(ps[i].y);
        ch.push_back(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);
    }
    
    for (int i = 1; i <= (n << 2 | 3); ++i) dist[i] = inf;
    
    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:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
flood.cpp:44: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:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &w);
     ~~~~~^~~~~~~~~~
flood.cpp:49: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

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	9720 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	9720 KB	Output is correct
2	Correct	9 ms	9992 KB	Output is correct
3	Correct	9 ms	9992 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	9992 KB	Output is correct

Subtask #4
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	9992 KB	Output is correct
2	Correct	10 ms	9992 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	9992 KB	Output is correct
2	Correct	9 ms	10016 KB	Output is correct

Subtask #6
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	10052 KB	Output is correct

Subtask #7
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	10092 KB	Output is correct

Subtask #8
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	10092 KB	Output is correct
2	Correct	10 ms	10092 KB	Output is correct

Subtask #9
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	10092 KB	Output is correct
2	Correct	10 ms	10172 KB	Output is correct

Subtask #10
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	13884 KB	Output is correct

Subtask #11
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	143 ms	24320 KB	Output is correct

Subtask #12
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	220 ms	26660 KB	Output is correct
2	Correct	507 ms	32732 KB	Output is correct

Subtask #13
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	418 ms	32732 KB	Output is correct
2	Runtime error	525 ms	33792 KB	Memory limit exceeded

Subtask #14
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	457 ms	33792 KB	Memory limit exceeded
2	Halted	0 ms	0 KB	-