QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#741766 | #9431. The Quest for El Dorado | xly_tyty# | WA | 146ms | 58140kb | C++23 | 1.2kb | 2024-11-13 15:11:06 | 2024-11-13 15:11:07 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const long long N=1e6+10,mod=998244353,INF=1e15;
ll n,m,k,a[N];
bool st[N];
struct node
{
int v,c,l;
};
vector<node>p[N];
multiset<pii>s[N];
vector<int>f;
void add(int u)
{
st[u]=1;
for(auto x:p[u])
{
if(!st[x.v])s[x.c].insert({x.l,x.v});
}
}
void dfs(int u,int w,int ty)
{
f.push_back(u);
st[u]=1;
for(auto it:p[u])
{
int v=it.v,c=it.c,l=it.l;
if(st[v]||c!=ty||l>w)continue;
dfs(v,l-w,ty);
}
}
void solve()
{
cin>>n>>m>>k;
for(int i=1;i<=max(n,m);i++)p[i].clear(),s[i].clear(),st[i]=0;
for(int i=1;i<=m;i++)
{
int u,v,c,l;cin>>u>>v>>c>>l;
p[u].push_back({v,c,l});
p[v].push_back({u,c,l});
}
add(1);
for(int i=1;i<=k;i++)
{
int c,l;cin>>c>>l;
f.clear();
while(s[c].size())
{
auto it=*s[c].begin();
if(it.first<=l)
{
s[c].erase(s[c].find(it));
dfs(it.second,l-it.first,c);
}
else break;
}
for(int x:f)add(x);
}
for(int i=1;i<=n;i++)cout<<st[i];cout<<endl;
}
signed main()
{
cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
int T;cin>>T;
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 53736kb
input:
2 5 6 4 1 2 1 30 2 3 1 50 2 5 5 50 3 4 6 10 2 4 5 30 2 5 1 40 1 70 6 100 5 40 1 30 3 1 1 2 3 1 10 1 100
output:
11011 100
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 146ms
memory: 58140kb
input:
1110 46 80 30 44 23 5 46 10 28 1 64 32 34 3 40 9 36 1 26 15 14 5 95 38 19 2 34 2 17 4 183 10 38 2 81 5 15 2 83 31 38 3 100 40 30 1 53 41 10 1 193 29 20 5 18 14 41 3 78 8 16 5 74 46 13 3 78 44 28 3 45 1 40 3 133 5 32 1 108 22 26 2 83 10 38 1 77 11 40 1 11 17 21 2 66 41 46 3 98 9 36 2 25 40 18 1 19 27...
output:
1000110001100101110010000001010100100101000000 1100010010111011011011000000011000001100001000 1000000000000000000000000000000000000000000000 1011010000000010000100010011000100000000000010 1000000000000000000000101000010000001001000001 1001100010110000100001100000000011001110110 101010000000000000010...
result:
wrong answer 1st lines differ - expected: '1000110011110111110010100001010100100101000000', found: '1000110001100101110010000001010100100101000000'