QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#108663#6335. Belt Conveyorikaurov0 0ms0kbC++173.8kb2023-05-25 22:33:192023-05-25 22:33:21

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-25 22:33:21]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-05-25 22:33:19]
  • 提交

answer

#include "conveyor.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
// #define endl '\n'

const int N = 1e5 + 20;

vector<int> g[N];
vector<int> active;
map<pair<int, int>, int> idx;
vector<int> lastquery, putball, nextdir, dir;

void setansdir(int u, int v){
  if (idx.count(pair{u, v})) dir[idx[{u, v}]] = 0;
  if (idx.count(pair{v, u})) dir[idx[{v, u}]] = 1;
}

void setnextdir(int u, int v){
  int id, needdir;
  if (idx.count(pair{u, v})){
    id = idx[{u, v}], needdir = 0;
  }
  else if (idx.count(pair{v, u})) id = idx[{v, u}], needdir = 1;
  else return;
  nextdir[id] = needdir ^ dir[id];
}

void process1(vector<int> path){
  int start = (sz(path) % 3 == 2? 1 : 0);
  for (int i = start; i < sz(path) - 1; i += 3) putball[path[i]] = 1;
}

void process2(vector<int> path){
  int start = (sz(path) % 3 == 2? 1 : 2);
  for (int i = start; i < sz(path) - 1; i += 3){
    if (lastquery[path[i]]){
      setansdir(path[i - 1], path[i]);
      setansdir(path[i + 1], path[i]);
    }
    else if (path[i - 1] != -1 && lastquery[path[i - 1]]){
      setansdir(path[i], path[i - 1]);
      setnextdir(path[i - 1], path[i]);
    }
    else{
      setansdir(path[i], path[i + 1]);
      setnextdir(path[i + 1], path[i]);
    }
    putball[path[i]] = 1;
  }
}

void process3(vector<int> path){
  int start = (sz(path) % 3 == 2? 1 : 2);
  for (int i = start; i < sz(path) - 1; i += 3){
    if (lastquery[path[i]]){
      setansdir(path[i - 1], path[i]);
      setansdir(path[i + 1], path[i]);
    }
    else if (path[i - 1] != -1 && lastquery[path[i - 1]]){
      setansdir(path[i], path[i - 1]);
    }
    else{
      setansdir(path[i], path[i + 1]);
    }
    setnextdir(path[i], path[i - 1]);
    setnextdir(path[i], path[i + 1]);
  }
  for (int i = (start == 1? 2 : 0); i < sz(path) - 1; i += 3){
    if (i) putball[path[i]] = 1;
    else putball[path[i + 1]] = 1;
  }
}

void process4(vector<int> path){
  int start = (sz(path) % 3 == 2? 1 : 2);
  for (int i = (start == 1? 2 : 0); i < sz(path) - 1; i += 3){
    if (lastquery[path[i]]) setansdir(path[i + 1], path[i]);
    else setansdir(path[i], path[i + 1]);
  }
  setnextdir(path[1], path[0]);
  setnextdir(path.end()[-2], path.end()[-1]);
  for (auto i : path) active[i] = 0;
}

vector<vector<int>> paths;
vector<int> curpath;

void dfs1(int v, int p){
  if (v != p) g[v].erase(find(all(g[v]), p));
  for (auto u : g[v]){
    dfs1(u, v);
  }
}

void dfs2(int v, int p){
  int c = 0;
  for (auto u : g[v]){
    c += active[u];
  }
  if (c <= 1){
    if (curpath.empty()){
      curpath.pb(p != v && active[p]? p : -1);
    }
    curpath.pb(v);
  }
  if (c == 0){
    curpath.pb(-1);
    if (sz(curpath) > 3 || curpath[0] != -1) paths.pb(curpath);
    curpath.clear();
  }
  if (!curpath.empty() && p != v && p == curpath.back()){
    curpath.pb(v);
    paths.pb(curpath);
    curpath.clear();
  }
  for (auto u : g[v]){
    dfs2(u, v);
  }
}

void Solve(int n, std::vector<int> a, std::vector<int> b){
  for (int i = 0; i < n - 1; i++){
    idx[{a[i], b[i]}] = i;
    g[a[i]].pb(b[i]);
    g[b[i]].pb(a[i]);
  }
  active = vector<int>(n, 1);
  putball = vector<int>(n, 0);
  dir = vector<int>(n - 1, 0);
  nextdir = vector<int>(n - 1, 0);
  dfs1(0, 0);
  while (1){
    dfs2(0, 0);
    if (paths.empty()) break;
    for (auto p : paths) process1(p);
    lastquery = Query(nextdir, putball);
    fill(all(putball), 0);
    for (auto p : paths) process2(p);
    lastquery = Query(nextdir, putball);
    fill(all(putball), 0);
    for (auto p : paths) process3(p);
    lastquery = Query(nextdir, putball);
    fill(all(putball), 0);
    for (auto p : paths) process4(p);
    fill(all(putball), 0);
  }
  Answer(dir);
}

详细

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

random1
2
0
1
1
0xC321A02965AC2640

output:

Unauthorized output

result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Runtime Error

Test #11:

score: 0
Runtime Error

input:

random1
100000
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...

output:

Unauthorized output

result:


Subtask #4:

score: 0
Skipped

Dependency #1:

0%