QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#108660#6335. Belt ConveyorikaurovCompile Error//C++174.5kb2023-05-25 22:30:252023-05-25 22:30:28

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:30:28]
  • 评测
  • [2023-05-25 22:30:25]
  • 提交

answer

#include "conveyor.h"
#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'

vector<int> Query(vector<int> x, vector<int> y){
  cout << "?" << endl;
  for (auto i : x) cout << i << " ";
  cout << endl;
  for (auto i : y) cout << i << " ";
  cout << endl;
  vector<int> ans(sz(y));
  for (auto &i : ans) cin >> i;
  return ans;
}

void Answer(vector<int> x){
  cout << "! ";
  for (auto i : x) cout << i << " ";
  cout << endl;
}

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);
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  // cout.precision(20);
  int n;
  cin >> n;
  vector<int> a(n - 1), b(n - 1);
  for (int i = 0; i < n - 1; i++) cin >> a[i] >> b[i];
  Solve(n, a, b);
}

詳細信息

/usr/bin/ld: /tmp/ccI5WEsX.o: in function `Answer(std::vector<int, std::allocator<int> >)':
answer.code:(.text+0x50): multiple definition of `Answer(std::vector<int, std::allocator<int> >)'; /tmp/cclBwudX.o:implementer.cpp:(.text+0x4d0): first defined here
/usr/bin/ld: /tmp/ccI5WEsX.o: in function `Query(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)':
answer.code:(.text+0x2c0): multiple definition of `Query(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'; /tmp/cclBwudX.o:implementer.cpp:(.text+0x670): first defined here
/usr/bin/ld: /tmp/ccI5WEsX.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/cclBwudX.o:implementer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status