QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #473315 | #7752. The Only Way to the Destination | zttttt | WA | 8ms | 51076kb | C++14 | 6.2kb | 2024-07-12 01:30:23 | 2024-07-12 01:30:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N=1e5+10,M=1e6+10;
struct S{
int x1,x2,y;
}s[N];
vector<pair<int,int>>v[M];
vector<int>vv[M];
int cnt,cnt1,zt[M],cot,ztt[M],pre[M],zqx,mp[M];
//struct SS{
// int s,x,djg;
//}p[M];
pair<int,int>p[M];
string ans;
int flag;
int find(int x){
if(pre[x]==0){
return x;
}else{
pre[x]=find(pre[x]);
return pre[x];
}
}
bool cmp(S x,S y1){
if(x.y!=y1.y){
return x.y<y1.y;
}else{
return x.x1<y1.x1;
}
}
int main(){
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++){
int x1,x2,y;
scanf("%d%d%d",&x1,&x2,&y);
s[i]={x1,x2,y};
}
sort(s+1,s+1+k,cmp);
return 0;
int cntt=0,syg=s[1].y;
// cnt++;
// cnt1++;
// zt[cnt]=cnt1;
// p[cnt1]={s[]}
int kt=s[1].y;
if(kt>=3){
cout<<"NO"<<endl;
return 0;
}
int kw=s[k].y;
if(m-kw>=2){
cout<<"NO"<<endl;
return 0;
}
if(kw-kt>=2*(k-1)+1){
cout<<"NO"<<endl;
return 0;
}
if(m>=2*k+2){
cout<<"NO"<<endl;
return 0;
}
int qd=1;
//puts("fuck");
int ix=max((int)1,kt-1);
int id=min(m,kw+1);
for(int i1=ix;i1<=id;i1++){
int i=i1-ix+1;
int syg=1;
for(int j=qd;j<=k;j++){
if(s[j].y==i1){
if(s[j].x1>syg){
v[i].push_back({syg,s[j].x1-1});
cnt1++;
vv[i].push_back(cnt1);
}
syg=s[j].x2+1;
}else{
qd=j;
break;
}
}
if(syg<=n){
v[i].push_back({syg,n});
cnt1++;
vv[i].push_back(cnt1);
}
}
//cout<<"fuck"<<endl;
//cout<<v[1].size()<<endl;
for(int i=ix;i<id;i++){
int i1=i-ix+1;
int cnt=v[i1].size()-1,cot=v[i1+1].size()-1;
//cout<<cnt<<" "<<cot<<endl;
int l=0,r=0;
//cout<<i<<endl;
while(1){
//cout<<l<<" "<<r<<endl;
if(l>cnt||r>cot)break;
if(v[i1][l].second<v[i1+1][r].first){
l++;
}else if(v[i1][l].second-v[i1+1][r].first>=1&&v[i1+1][r].second-v[i1][l].first>=1&&v[i1][l].second-v[i1][l].first>=1){
ans="NO";
flag=1;
break;
}else if(v[i1][l].second==v[i1+1][r].first){
if(find(vv[i1][l])==vv[i1][l]&&find(vv[i1+1][r])==vv[i1+1][l]){
// zqx++;
// if(zqx>1){
// ans="NO";
// flag=1;
// break;
// }else{
pre[find(vv[i1][l])]=find(vv[i1+1][r]);
// }
}else{
if(find(vv[i1][l])!=find(vv[i1+1][r])){
pre[find(vv[i1][l])]=find(vv[i1+1][r]);
}else{
ans="NO";
flag=1;
break;
}
}
l++;
}else if(v[i1][l].first==v[i1+1][r].second){
if(find(vv[i1][l])==vv[i1][l]&&find(vv[i1+1][r])==vv[i1+1][l]){
// zqx++;
// if(zqx>1){
// ans="NO";
// flag=1;
// break;
// }else{
pre[find(vv[i1][l])]=find(vv[i1+1][r]);
//}
}else{
if(find(vv[i1][l])!=find(vv[i1+1][r])){
pre[find(vv[i1][l])]=find(vv[i1+1][r]);
}else{
ans="NO";
flag=1;
break;
}
}
r++;
}else if(v[i1][l].first>v[i1+1][r].second){
r++;
}
}
if(flag)break;
}
// for(int i=1;i<=k;i++){
// if(s[i].y==syg&&cntt==0){
// if(i>=2){
// if(s[i].x1-s[i-1].x2>1){
// cnt++;
// cnt1++;
// zt[cnt]=cnt1;
// p[cnt1]={s[i-1].x2+1,s[i].x1-1};
// }
// }else{
// if(s[i].x1>1){
// cnt++;
// cnt1++;
// p[cnt1]={1,s[i].x1-1};
// zt[cnt]=cnt1;
// }
// }
// }else if(s[i].y!=syg&&cntt==0){
// cntt++;
// syg=s[i].y;
// if(i>=2){
// if(s[i].x1-s[i-1].x2>1){
// cot++;
// cnt1++;
// ztt[cot]=cnt1;
// p[cnt1]={s[i-1].x2+1,s[i].x1-1};
// }
// }else{
// if(s[i].x1>1){
// cot++;
// cnt1++;
// p[cnt1]={1,s[i].x1-1};
// ztt[cot]=cnt1;
// }
// }
// }else if(cntt==1&&s[i].y==syg){
// if(i>=2){
// if(s[i].x1-s[i-1].x2>1){
// cot++;
// cnt1++;
// ztt[cot]=cnt1;
// p[cnt1]={s[i-1].x2+1,s[i].x1-1};
// }
// }else{
// if(s[i].x1>1){
// cot++;
// cnt1++;
// p[cnt1]={1,s[i].x1-1};
// ztt[cot]=cnt1;
// }
// }
// }else if(cntt>=1&&s[i].y!=syg){
// int l=1;
// int r=1;
// while(1){
// if(l>cnt||r>cot)break;
// if(p[zt[l]].second<p[ztt[r]].first){
// l++;
// }else if(p[zt[l]].second-p[ztt[r]].first>=1&&p[ztt[r]].second-p[zt[l]].second>=1){
// ans="NO";
// flag=1;
// break;
// }else if(p[zt[l]].second==p[ztt[r]].first){
// if(find(zt[l])==0&&find(ztt[r])==0){
// zqx++;
// if(zqx>1){
// ans="NO";
// flag=1;
// break;
// }else{
//
// pre[find(zt[l])]=find(ztt[r]);
//
// }
// }else{
// if(find(zt[l])!=find(ztt[r])){
// pre[find(zt[l])]=find(ztt[r]);
// }else{
// ans="NO";
// flag=1;
// break;
// }
// }
// l++;
// }else if(p[zt[l]].first==p[ztt[r]].second){
// if(find(zt[l])==0&&find(ztt[r])==0){
// zqx++;
// if(zqx>1){
// ans="NO";
// flag=1;
// break;
// }else{
//
// pre[find(zt[l])]=find(ztt[r]);
//
// }
// }else{
// if(find(zt[l])!=find(ztt[r])){
// pre[find(zt[l])]=find(ztt[r]);
// }else{
// ans="NO";
// flag=1;
// break;
// }
// }
// r++;
// }else if(p[zt[l]].first>p[ztt[r]].second){
// r++;
// }
//
// }
// if(flag)break;
// cntt++;
// for(int j=1;j<=cot;j++)zt[j]=ztt[j];
// cot=0;
// syg=s[i].y;
// }else if(cntt>=1&&s[i].y==syg){
// if(i>=2){
// if(s[i].x1-s[i-1].x2>1){
// cot++;
// cnt1++;
// ztt[cot]=cnt1;
// p[cnt1]={s[i-1].x2+1,s[i].x1-1};
// }
// }else{
// if(s[i].x1>1){
// cot++;
// cnt1++;
// p[cnt1]={1,s[i].x1-1};
// ztt[cot]=cnt1;
// }
// }
// }
// }
if(flag==1)cout<<"NO"<<endl;
else{
for(int i=ix;i<=id;i++){
int i1=i-ix+1;
for(int j=0;j<vv[i1].size();j++){
int zy=find(vv[i1][j]);
if(mp[zy]==0){
mp[zy]=1;
zqx++;
}
if(zqx>1){
flag=1;
break;
}
}
if(flag)break;
}
if(flag)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 8ms
memory: 51076kb
input:
5 3 2 2 5 1 1 4 3
output:
result:
wrong output format Unexpected end of file - token expected