답안 #1020658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1020658	2024-07-12T08:08:21 Z	NeroZein	분수 공원 (IOI21_parks)	C++17	5 / 100	373 ms	58976 KB

parks

#include "parks.h"
#include <bits/stdc++.h>

using namespace std; 

const int MAXY = 2e5 + 5; 

map<pair<int, int>, int> mp;
vector<pair<int, int>> inY[MAXY];

int construct_roads(vector<int> x, vector<int> y) {
  int n = (int) x.size();
  for (int i = 0; i < n; ++i) {
    inY[y[i]].emplace_back(x[i], i); 
    mp[{x[i], y[i]}] = i;
  }
  vector<int> u, v, a, b;
  vector<vector<int>> g(n); 
  auto addedge = [&](int uu, int vv, int aa, int bb) {
    u.push_back(uu);
    v.push_back(vv);
    a.push_back(aa);
    b.push_back(bb);
    g[uu].push_back(vv);
    g[vv].push_back(uu);
    //cout << "u, v, a, b: " << uu << ' ' << vv << ' ' << aa << ' ' << bb << '\n'; 
  };
  for (int cury = 2; cury < MAXY; cury += 2) {//add vertical lines
    int cnt = 0;
    sort(inY[cury].begin(), inY[cury].end());
    for (int j = 0; j < (int) inY[cury].size(); ++j) {
      auto [curx, id] = inY[cury][j];
      if (mp.count({curx, cury + 2})) {
        cnt++; 
      }
    }
    for (int j = 0; j < (int) inY[cury].size(); ++j) {
      auto [curx, id] = inY[cury][j];
      if (!mp.count({curx, cury + 2})) {
        continue; 
      }
      if (curx == 2) {
        addedge(id, mp[{curx, cury + 2}], curx - 1, cury + 1);
      } else if (curx == 6) {
        addedge(id, mp[{curx, cury + 2}], curx + 1, cury + 1);
      } else if (cnt == 1) {
        addedge(id, mp[{curx, cury + 2}], curx + (cury % 4 == 0 ? -1 : 1), cury + 1);
      }
    }
  }
  for (int cury = 2; cury < MAXY; cury += 2) {//add horizontal lines (x, y) -> (x + 2, y)
    for (int j = 0; j < (int) inY[cury].size() - 1; ++j) {
      auto [curx, id] = inY[cury][j];
      if (cury % 4 == 0) {
        addedge(id, inY[cury][j + 1].second, curx + 1, cury + (curx == 2 ? -1 : 1));
      } else {
        addedge(id, inY[cury][j + 1].second, curx + 1, cury + (curx == 2 ? 1 : -1)); 
      }
    }
  }
  vector<bool> vis(n);
  function<void(int)> dfs = [&](int nd) {
    vis[nd] = true;
    //cout << "ND: " << nd << '\n'; 
    for (int ch : g[nd]) {
      if (!vis[ch]) {
        dfs(ch);        
      }
    }
  };
  dfs(0); 
  for (int i = 0; i < n; ++i) {
    if (!vis[i]) {
      return 0; 
    }
  }
  build(u, v, a, b); 
  return 1;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4956 KB	Output is correct
2	Correct	3 ms	5212 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Correct	3 ms	4956 KB	Output is correct
5	Correct	3 ms	4956 KB	Output is correct
6	Correct	3 ms	5128 KB	Output is correct
7	Correct	3 ms	4956 KB	Output is correct
8	Correct	2 ms	4956 KB	Output is correct
9	Correct	151 ms	32704 KB	Output is correct
10	Correct	15 ms	7972 KB	Output is correct
11	Correct	54 ms	20236 KB	Output is correct
12	Correct	15 ms	9308 KB	Output is correct
13	Correct	30 ms	15308 KB	Output is correct
14	Correct	6 ms	5212 KB	Output is correct
15	Correct	5 ms	5468 KB	Output is correct
16	Correct	150 ms	30136 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4956 KB	Output is correct
2	Correct	3 ms	5212 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Correct	3 ms	4956 KB	Output is correct
5	Correct	3 ms	4956 KB	Output is correct
6	Correct	3 ms	5128 KB	Output is correct
7	Correct	3 ms	4956 KB	Output is correct
8	Correct	2 ms	4956 KB	Output is correct
9	Correct	151 ms	32704 KB	Output is correct
10	Correct	15 ms	7972 KB	Output is correct
11	Correct	54 ms	20236 KB	Output is correct
12	Correct	15 ms	9308 KB	Output is correct
13	Correct	30 ms	15308 KB	Output is correct
14	Correct	6 ms	5212 KB	Output is correct
15	Correct	5 ms	5468 KB	Output is correct
16	Correct	150 ms	30136 KB	Output is correct
17	Incorrect	3 ms	4956 KB	Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4956 KB	Output is correct
2	Correct	3 ms	5212 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Correct	3 ms	4956 KB	Output is correct
5	Correct	3 ms	4956 KB	Output is correct
6	Correct	3 ms	5128 KB	Output is correct
7	Correct	3 ms	4956 KB	Output is correct
8	Correct	2 ms	4956 KB	Output is correct
9	Correct	151 ms	32704 KB	Output is correct
10	Correct	15 ms	7972 KB	Output is correct
11	Correct	54 ms	20236 KB	Output is correct
12	Correct	15 ms	9308 KB	Output is correct
13	Correct	30 ms	15308 KB	Output is correct
14	Correct	6 ms	5212 KB	Output is correct
15	Correct	5 ms	5468 KB	Output is correct
16	Correct	150 ms	30136 KB	Output is correct
17	Incorrect	3 ms	4956 KB	Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4956 KB	Output is correct
2	Correct	3 ms	5212 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Correct	3 ms	4956 KB	Output is correct
5	Correct	3 ms	4956 KB	Output is correct
6	Correct	3 ms	5128 KB	Output is correct
7	Correct	3 ms	4956 KB	Output is correct
8	Correct	2 ms	4956 KB	Output is correct
9	Correct	151 ms	32704 KB	Output is correct
10	Correct	15 ms	7972 KB	Output is correct
11	Correct	54 ms	20236 KB	Output is correct
12	Correct	15 ms	9308 KB	Output is correct
13	Correct	30 ms	15308 KB	Output is correct
14	Correct	6 ms	5212 KB	Output is correct
15	Correct	5 ms	5468 KB	Output is correct
16	Correct	150 ms	30136 KB	Output is correct
17	Correct	2 ms	4956 KB	Output is correct
18	Correct	4 ms	4956 KB	Output is correct
19	Correct	3 ms	4956 KB	Output is correct
20	Incorrect	373 ms	58976 KB	Tree @(199997, 5) appears more than once: for edges on positions 1 and 100000
21	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4956 KB	Output is correct
2	Correct	3 ms	5212 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Correct	3 ms	4956 KB	Output is correct
5	Correct	3 ms	4956 KB	Output is correct
6	Correct	3 ms	5128 KB	Output is correct
7	Correct	3 ms	4956 KB	Output is correct
8	Correct	2 ms	4956 KB	Output is correct
9	Correct	151 ms	32704 KB	Output is correct
10	Correct	15 ms	7972 KB	Output is correct
11	Correct	54 ms	20236 KB	Output is correct
12	Correct	15 ms	9308 KB	Output is correct
13	Correct	30 ms	15308 KB	Output is correct
14	Correct	6 ms	5212 KB	Output is correct
15	Correct	5 ms	5468 KB	Output is correct
16	Correct	150 ms	30136 KB	Output is correct
17	Incorrect	291 ms	54328 KB	Pair u[100000]=112394 @(2, 4) and v[100000]=87394 @(100002, 4) does not form a valid edge (distance != 2)
18	Halted	0 ms	0 KB	-

Subtask #6
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4956 KB	Output is correct
2	Correct	3 ms	5212 KB	Output is correct
3	Correct	3 ms	4956 KB	Output is correct
4	Correct	3 ms	4956 KB	Output is correct
5	Correct	3 ms	4956 KB	Output is correct
6	Correct	3 ms	5128 KB	Output is correct
7	Correct	3 ms	4956 KB	Output is correct
8	Correct	2 ms	4956 KB	Output is correct
9	Correct	151 ms	32704 KB	Output is correct
10	Correct	15 ms	7972 KB	Output is correct
11	Correct	54 ms	20236 KB	Output is correct
12	Correct	15 ms	9308 KB	Output is correct
13	Correct	30 ms	15308 KB	Output is correct
14	Correct	6 ms	5212 KB	Output is correct
15	Correct	5 ms	5468 KB	Output is correct
16	Correct	150 ms	30136 KB	Output is correct
17	Incorrect	3 ms	4956 KB	Tree @(3, 3) appears more than once: for edges on positions 1 and 2
18	Halted	0 ms	0 KB	-

답안 #1020658

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 10.0

Subtask #3 0 / 15.0

Subtask #4 0 / 20.0

Subtask #5 0 / 20.0

Subtask #6 0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
0 / 20.0

Subtask #5
0 / 20.0

Subtask #6
0 / 30.0