QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #141363 | #6520. Classic Problem | cy1999 | WA | 345ms | 18964kb | C++20 | 1.1kb | 2023-08-17 11:10:00 | 2023-08-17 11:10:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int> nxt,val;
map<pair<int,int>,int> lim;
vector<int> t;
int n,m;
long long ans=0;
int &getnxt(int u){
if(nxt.find(u)==nxt.end()) nxt[u]=u+1;
return nxt[u];
}
void solve(){
t.clear();
val.clear();
lim.clear();
nxt.clear();
cin>>n>>m;
ans=n-1;
for(int i=1; i<=m; i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
lim[make_pair(u,v)]=1;
t.emplace_back(u);
if(val.find(u)==val.end()) val[u]=w;
else val[u]=min(val[u],w);
}
sort(t.begin(),t.end());
t.erase(unique(t.begin(),t.end()),t.end());
reverse(t.begin(),t.end());
for(auto p:t){
while(lim.find(make_pair(p,getnxt(p)))!=lim.end()){
getnxt(p)=getnxt(getnxt(p));
}
if(getnxt(p)!=n+1) val[p]=min(val[p],getnxt(p)-p);
}
for(auto p:t){
// cout<<p<<' '<<val[p]<<endl;
ans--;
ans+=val[p];
}
cout<<ans<<'\n';
}
int main(){
int T;
cin>>T;
while(T--) solve();
return 0;
}
/*
3
5 3
1 2 5
2 3 4
1 5 0
5 0
5 4
1 2 1000000000
1 3 1000000000
1 4 1000000000
1 5 1000000000
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3508kb
input:
3 5 3 1 2 5 2 3 4 1 5 0 5 0 5 4 1 2 1000000000 1 3 1000000000 1 4 1000000000 1 5 1000000000
output:
4 4 1000000003
result:
ok 3 number(s): "4 4 1000000003"
Test #2:
score: -100
Wrong Answer
time: 345ms
memory: 18964kb
input:
16 1000000000 0 447 99681 1 2 1000000000 1 3 1000000000 2 3 1000000000 1 4 1000000000 2 4 1000000000 3 4 1000000000 1 5 1000000000 2 5 1000000000 3 5 1000000000 4 5 1000000000 1 6 1000000000 2 6 1000000000 3 6 1000000000 4 6 1000000000 5 6 1000000000 1 7 1000000000 2 7 1000000000 3 7 1000000000 4 7 ...
output:
999999999 446000000000 6077068954 999999680 999900005 999966832 749 196 3189 2594 2157 5808 228 1436 1649 211
result:
wrong answer 3rd numbers differ - expected: '732256441', found: '6077068954'