QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#131321 | #6570. Who Watches the Watchmen? | installb | Compile Error | / | / | C++14 | 6.6kb | 2023-07-26 22:14:17 | 2023-07-26 22:14:19 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-07-26 22:14:19]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-07-26 22:14:17]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
const int M = 1000005;
struct point{
int x,y,z; int id;
point (int _x = 0,int _y = 0,int _z = 0) : x(_x), y(_y), z(_z) {}
}p[N],d[N],sp[N],q[N];
int n;
bool cmp(point p1,point p2){
if(p1.x != p2.x) return p1.x < p2.x;
if(p1.y != p2.y) return p1.y < p2.y;
return p1.z < p2.z;
}
point simpl(const point &p){
int x = abs(__gcd(p.x,__gcd(p.y,p.z)));
return point(p.x / x,p.y / x,p.z / x);
}
point operator - (const point &p1,const point &p2){
return point(p1.x - p2.x,p1.y - p2.y,p1.z - p2.z);
}
point operator + (const point &p1,const point &p2){
return point(p1.x + p2.x,p1.y + p2.y,p1.z + p2.z);
}
point det(const point &p1,const point &p2){
return point(p1.y * p2.z - p1.z * p2.y,p1.z * p2.x - p1.x * p2.z,p1.x * p2.y - p1.y * p2.x);
}
ll dot(const point &p1,const point &p2){
return 1ll * p1.x * p2.x + 1ll * p1.y * p2.y + 1ll * p1.z * p2.z;
}
int len(const point &p){
return abs(p.x) + abs(p.y) + abs(p.z);
}
bool operator == (const point &p1,const point &p2){
return p1.x == p2.x && p1.y == p2.y && p1.z == p2.z;
}
bool operator != (const point &p1,const point &p2){
return p1.x != p2.x || p1.y != p2.y || p1.z != p2.z;
}
bool eq(const point &p1,const point &p2){
return simpl(p1) == simpl(p2) || simpl(p1) == point(0,0,0) - simpl(p2);
} // parallel
bool eq2(const point &p1,const point &p2){
return simpl(p1) == simpl(p2);
} // same direction
void input(point &p){
cin >> p.x >> p.y >> p.z;
}
int ec = 1,to[M << 1],nxt[M << 1],cap[M << 1],w[M << 1];
int hed[N];
void add_edge(int f,int t,int c,int d){
++ ec; to[ec] = t; nxt[ec] = hed[f]; hed[f] = ec; cap[ec] = c; w[ec] = d;
++ ec; to[ec] = f; nxt[ec] = hed[t]; hed[t] = ec; cap[ec] = 0; w[ec] = -d;
}
int dis[N],inq[N],flw[N],pre[N],prv[N];
const int INF = 0x3f3f3f3f;
int spfa(int s,int t){
for(int i = 1;i <= t;i ++){
dis[i] = INF; inq[i] = 0; flw[i] = 0;
}
prv[t] = -1;
queue <int> q;
q.push(s); inq[s] = 1; dis[s] = 0; flw[s] = INF;
while(!q.empty()){
int u = q.front(); q.pop();
inq[u] = 0;
for(int i = hed[u];i;i = nxt[i]){
int v = to[i];
if(dis[v] > dis[u] + w[i] && cap[i]){
dis[v] = dis[u] + w[i];
prv[v] = u;
pre[v] = i;
flw[v] = min(flw[u],cap[i]);
if(!inq[v]){
q.push(v);
inq[v] = 1;
}
}
}
}
return prv[t] != -1;
}
int mcf = 0,mxf = 0;
void mcmf(int s,int t){
while(spfa(s,t)){
mxf += flw[t];
mcf += flw[t] * dis[t];
int now = t;
while(now != s){
cap[pre[now]] -= flw[t];
cap[pre[now] ^ 1] += flw[t];
now = prv[now];
}
}
}
void solve(){
cin >> n;
for(int i = 1;i <= n;i ++){
input(p[i]);
input(d[i]);
p[i].id = i;
}
if(n == 1){
cout << -1 << '\n';
return 0;
}
int S = n + n + 1;
int T = S + 1;
for(int i = 1;i <= n;i ++){
point di = simpl(d[i]);
for(int j = 1;j <= n;j ++) if(j != i) sp[j] = simpl(p[j] - p[i]);
for(int j = 1;j <= n;j ++){
if(i == j) continue;
int fl = 0;
for(int k = 1;k <= n;k ++){
if(k == i || k == j) continue;
if(sp[k] == sp[j] && len(p[k] - p[i]) < len(p[j] - p[i])){
fl = 1; break;
}
}
if(!fl){
if(sp[j] == di) add_edge(i,j + n,1,0);
else add_edge(i,j + n,1,1);
}
}
add_edge(S,i,1,0);
add_edge(i + n,T,1,0);
}
mcmf(S,T);
if(mxf == n){
cout << mcf << '\n';
return;
}
int del = 0;
for(int id = 1;id <= n;id ++){
int qc = 0;
for(int i = 1;i <= n;i ++){
if(i == id) continue;
q[++ qc] = p[i];
}
sort(q + 1,q + 1 + qc,cmp);
vector <int> tor(qc + 2),fromr(qc + 2),pre(qc + 2),suf(qc + 2);
tor[0] = fromr[0] = 0;
for(int i = 1;i < qc;i ++){
tor[i] = tor[i - 1];
fromr[i] = fromr[i - 1];
if(eq2(d[q[i].id],q[i + 1] - q[i])) tor[i] ++;
if(eq2(d[q[i + 1].id],q[i] - q[i + 1])) fromr[i] ++;
}
pre[0] = suf[qc + 1] = 0;
for(int i = 2;i <= qc;i += 2){
pre[i] = pre[i - 2];
if(eq2(d[q[i - 1].id],q[i] - q[i - 1])) pre[i] ++;
if(eq2(d[q[i].id],q[i - 1] - q[i])) pre[i] ++;
}
for(int i = qc - 1;i >= 1;i -= 2){
suf[i] = suf[i + 2];
if(eq2(d[q[i].id],q[i + 1] - q[i])) suf[i] ++;
if(eq2(d[q[i + 1].id],q[i] - q[i + 1])) suf[i] ++;
}
for(int l = 1;l <= qc;l += 2){
for(int r = qc;r >= l;r -= 2){
int cur = 0,lrs = 0;
lrs = pre[l - 1] + suf[r + 1];
// id -> l -> r -> id, d[id], d[r], l->r(q[r] - q[l]) froms a triangle
cur = tor[r - 1] - tor[l - 1];
if(l != r && eq(d[id],q[r] - q[l]) && eq(d[q[r].id],q[r] - q[l])) cur += 0;
else if((l != r && !eq(q[r] - q[l],d[q[r].id]) && !eq(q[r] - q[l],d[id]) && !eq(d[q[r].id],d[id]) && dot(det(q[r] - q[l],d[q[r].id]),d[id]) == 0) || (l == r && simpl(point(0,0,0) - d[q[l].id]) == simpl(d[id]))) cur += 2;
else cur ++;
del = max(del,cur + lrs);
// id -> r -> l -> id
cur = fromr[r - 1] - fromr[l - 1];
if(l != r && eq(d[id],q[r] - q[l]) && eq(d[q[l].id],q[r] - q[l])) cur += 0;
else if((l != r && !eq(q[r] - q[l],d[q[l].id]) && !eq(q[r] - q[l],d[id]) && !eq(d[q[l].id],d[id]) && dot(det(q[r] - q[l],d[q[l].id]),d[id]) == 0) || (l == r && simpl(point(0,0,0) - d[q[l].id]) == simpl(d[id]))) cur += 2;
else cur ++;
del = max(del,cur + lrs);
// cout << id << ' ' << l << ' ' << r << ' ' << cur + lrs << endl;
// cout << d[q[l].id].x << ',' << d[q[l].id].y << ' ' << d[id].x << ',' << d[id].y << '(' << eq(d[q[l].id],d[id]) << ' ' << eq(d[q[r].id],d[id]) << ')' << tor[r - 1] - tor[l - 1] << ' ' << fromr[r - 1] - fromr[l - 1] << '\n';
}
}
}
cout << 1000 + n - del << '\n';
}
int main(){
ios::sync_with_stdio(false);
solve();
return 0;
}
Details
answer.code: In function ‘void solve()’: answer.code:127:16: error: return-statement with a value, in function returning ‘void’ [-fpermissive] 127 | return 0; | ^