QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#787242 | #9802. Light Up the Grid | tilenn | TL | 0ms | 0kb | C++14 | 1.9kb | 2024-11-27 10:32:04 | 2024-11-27 10:32:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n';
typedef long long LL;
typedef unsigned long long ULL;
vector<LL> a(4);
vector<pair<ULL,LL>> md;
vector<LL> dist(1 << 16,1e18);
void init(){
priority_queue<pair<LL,pair<ULL,LL>>,vector<pair<LL,pair<ULL,LL>>>,greater<pair<LL,pair<ULL,LL>>>> q;
map<pair<ULL,LL>,LL> mp;
ULL s = 0;
for(int i = 0;i < 16;i++){
s |= ULL(i) << (4 * i);
}
q.push({0,{s,0}});
dist[0] = 0;
while(q.size()){
auto [w,_] = q.top();
auto [F,G] = _;
q.pop();
if(mp[_] < w)continue;
for(int i = G;i > 0;i = (i - 1) & G){
dist[i] = min(dist[i],w);
}
for(auto [t,c] : md){
auto f = F;
auto g = G;
for(int i = 0;i < 16;i++){
f ^= t << (4 * i);
if((f & (ULL(15) << (4 * i))) == (ULL(15) << (4 * i))){
g |= 1LL << i;
}
}
if(!mp.count({f,g}) || mp[{f,g}] > w + c){
mp[{f,g}] = w + c;
q.push({w + c,{f,g}});
}
}
}
}
void solve(){
int n;
cin >> n;
int s = 0;
for(int i = 1;i <= n;i++){
string x,y;
cin >> x >> y;
int z = 0;
z += 8 * (x[0] - '0');
z += 4 * (x[1] - '0');
z += 2 * (y[0] - '0');
z += (y[1] - '0');
s += 1 << z;
}
cout << dist[s] << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL),cout.tie(NULL);
int t = 1;
cin >> t;
cin >> a[0] >> a[1] >> a[2] >> a[3];
for(int i = 0;i < 4;i++){
md.push_back({1 << i,a[0]});
}
md.push_back({12,a[1]});
md.push_back({3,a[1]});
md.push_back({10,a[2]});
md.push_back({5,a[2]});
md.push_back({15,a[3]});
init();
while(t--){
solve();
}
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
2 1000 100 10 1 4 10 00 01 00 00 10 00 01 1 11 11