QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #756617 | #9730. Elevator II | hxsj# | WA | 193ms | 3848kb | C++14 | 3.6kb | 2024-11-16 21:12:36 | 2024-11-16 21:12:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int p[N];
void init(int n)
{
for(int i = 1;i<=n;i++)
{
p[i] = i;
}
}
int find(int x) // 并查集
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void merge(int x,int y)
{
x = find(x),y = find(y);
if(x!=y)
{
p[x] = p[y];
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
ll n, m;
cin >> n >> m;
init(n);
vector<array<ll,3>> poi(n+1);
for(int i = 1; i <= n ; i++){
cin >> poi[i][0]>>poi[i][1];
poi[i][2] = i;
}
sort(poi.begin(),poi.end());
for(int i = 2;i<=n;i++)
{
if(poi[i][0]<=poi[i-1][1])
{
merge(poi[i][2],poi[i-1][2]);
}
}
int index = n;
for(int i = 1;i<=n;i++)
{
if(poi[i][0]>=m)
{
index = i;
break;
}
}
ll ans = 0;
vector<int>inx;
map<int,int>mp;
ll now = m;
map<int,vector<array<ll,3>>>ap;
map<int,array<ll,3>>op;
for (int i = 1; i <= n; i ++ )
{
ap[find(i)].push_back({poi[i][0],poi[i][1],poi[i][2]});
if(op[find(i)][1]<=poi[i][1])
{
op[find(i)] = {poi[i][0],poi[i][1],poi[i][2]};
}
}
for(int i = index;i>=1;i--)
{
if(find(i)!=find(index))
{
break;
}
index = i;
}
//cout<<index<<"!"<<endl;
int lst = 0;
for (int i = index; i <= n; i ++ )
{
int fa = find(i);
if(mp[fa]==0)
{
mp[fa] = 1;
int nt = 0;
for(int j = 0;j<ap[fa].size();j++)
{
//cout<<ap[fa][j][0]<<" "<<ap[fa][j][1]<<" "<<ap[fa][j][2]<<endl;
if(ap[fa][j][2]!=op[fa][2])
{
nt++;
if(nt==1)ans+=max(0ll,ap[fa][j][0]-now);
ans+=ap[fa][j][1]-ap[fa][j][0];
inx.push_back(ap[fa][j][2]);
//now = ap[fa][j][0];
}
}
ans+=op[fa][1]-op[fa][0];
if(ap[fa].size()==1)
{
ans+=max(0ll,op[fa][0]-now);
}
inx.push_back(op[fa][2]);
now = op[fa][1];
}
}
for(int i = index-1;i>=1;i--)
{
int fa = find(i);
int nt = 0;
if(mp[fa]==0)
{
mp[fa] = 1;
for(int j = 0;j<ap[fa].size();j++)
{
if(ap[fa][j][2]!=op[fa][2])
{
ans+=ap[fa][j][1]-ap[fa][j][0];
inx.push_back(ap[fa][j][2]);
}
}
ans+=op[fa][1]-op[fa][0];
inx.push_back(op[fa][2]);
}
}
cout<<ans<<endl;
for(int i = 0;i<inx.size();i++)
{
cout<<inx[i]<<" ";
}
cout<<endl;
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3776kb
input:
2 4 2 3 6 1 3 2 7 5 6 2 5 2 4 6 8
output:
11 2 1 4 3 5 2 1
result:
ok ok 2 cases (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 193ms
memory: 3848kb
input:
6100 19 52 51 98 2 83 40 58 96 99 39 55 72 94 15 17 4 15 48 99 2 99 77 78 35 77 44 62 79 81 30 31 1 48 48 76 68 99 60 66 6 19 44 53 64 92 17 28 67 98 9 99 40 65 16 27 99 100 15 56 4 6 24 97 84 96 47 49 37 38 77 79 13 40 13 92 71 100 47 93 90 91 72 81 15 48 32 71 19 17 95 99 10 23 18 100 90 93 52 92 ...
output:
534 19 18 2 12 5 13 6 16 10 7 3 9 1 11 4 15 17 14 8 229 6 2 3 1 4 5 397 9 15 16 6 12 13 1 4 7 14 5 11 2 8 10 3 733 9 15 18 7 11 6 14 13 19 10 12 5 16 8 17 4 1 3 2 244 9 11 14 8 2 10 13 3 15 1 5 4 12 6 7 422 17 12 3 19 1 14 16 15 9 5 8 20 4 13 2 7 6 10 11 18 104 2 1 4 3 193 1 8 3 6 5 2 4 10 9 ...
result:
wrong answer Participant declares the cost to be 534, but the plan actually costs 605 (test case 1)