QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#56567 | #1972. JJ Rally | AmrMohameD | WA | 68ms | 364104kb | C++ | 3.0kb | 2022-10-20 05:57:09 | 2022-10-20 05:57:10 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define EPS 1e-9
#define PI acos(-1.0)
#define ll long long
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
#define pb push_back
#define ft first
#define sc second
#define pi pair<int,int>
#define vi vector<int>
#define sz(s) s.size()
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const ll N = 25, M = (1 << 20), MOD = (1LL<<32), INF = 1e18;
int dx[] = {-1, 1, 0, 0}, Dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};;
int dy[] = {0, 0, 1, -1}, Dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
ll n, m, t,dp[22][M],dp2[22][M], s1,s2,t1,t2,dis[N][N],mp[N];
vector<pi> g[25];
ll solve2(int node,int msk)
{
if(mp[t2] == node){
return 1;
}
ll &ret = dp2[node][msk];
if(~ret)
return ret;
ret = 0;
for(auto it:g[node])
{
if(it.ft != mp[s1] && it.ft != mp[t1] && it.ft != mp[s2] && dis[mp[s2]][node] + it.sc + dis[it.ft][mp[t2]] == dis[mp[s2]][mp[t2]] && !(msk&(1<<it.ft)))
ret += solve2(it.ft,msk|(1<<it.ft));
}
return ret;
}
ll solve(int node,int msk)
{
if(mp[t1] == node){
return solve2(mp[s2],msk);
}
ll &ret = dp[node][msk];
if(~ret)
return ret;
ret = 0;
for(auto it:g[node])
{
if(it.ft != mp[s2] && it.ft != mp[t2] && it.ft != mp[s1] && dis[mp[s1]][node] + it.sc + dis[it.ft][mp[t1]] == dis[mp[s1]][mp[t1]])
ret += solve(it.ft,msk|(1<<it.ft));
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);//freopen("lines.in", "r", stdin);
cin >> n >> m;
for(int i = 0; i < n ;++i)
{
dis[i][i] = 0;
for(int j = i+1; j < n ;++j)
{
dis[i][j] = dis[j][i] = 1e9;
}
}
vector<pair<pi,int>> tmp;
for(int i = 0; i < m ;++i)
{
int u,v,c;
cin >> u >> v >> c;
u--,v--;
tmp.pb({{u,v},c});
}
int id = 0;
cin >> s1 >> t1 >> s2 >> t2;
s1--,s2--,t1--,t2--;
for(int i = 0; i < n ;++i){
if(i == t1 || i == t2 or i == s1 or i == s2) continue;
mp[i] = id++;
}
mp[t1] = id++;
mp[t2] = id++;
mp[s1] = id++;
mp[s2] = id++;
for(int i = 0; i < m ;++i)
{
int u = mp[tmp[i].ft.ft] , v = mp[tmp[i].ft.sc] , c = tmp[i].sc;
dis[u][v] = dis[v][u] = c;
g[u].pb({v,c});
g[v].pb({u,c});
}
memset(dp,-1,sizeof dp);
memset(dp2,-1,sizeof dp2);
for(int i = 0; i < n ;++i)
{
for(int j = 0;j < n ;++j)
{
for(int k = 0; k < n ;++k)
{
dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]);
}
}
}
cout << solve(mp[s1],0);
return 0;
}
/*
*/
详细
Test #1:
score: 100
Accepted
time: 23ms
memory: 363952kb
input:
4 4 1 2 2 2 3 1 1 3 1 3 4 1 1 2 3 4
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 48ms
memory: 364008kb
input:
4 3 1 2 1 2 3 1 3 4 1 1 3 2 4
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 68ms
memory: 364100kb
input:
6 8 1 4 1 1 3 1 4 2 1 3 2 1 1 2 2 1 5 1 5 2 1 5 6 2 1 2 6 5
output:
3
result:
ok single line: '3'
Test #4:
score: -100
Wrong Answer
time: 47ms
memory: 364104kb
input:
24 276 1 2 117 1 3 36 1 4 247 1 5 150 1 6 215 1 7 232 1 8 161 1 9 209 1 10 190 1 11 4 1 12 102 1 13 281 1 14 301 1 15 32 1 16 138 1 17 114 1 18 304 1 19 141 1 20 105 1 21 64 1 22 75 1 23 23 1 24 237 2 3 153 2 4 364 2 5 267 2 6 332 2 7 349 2 8 278 2 9 326 2 10 307 2 11 113 2 12 219 2 13 398 2 14 418 ...
output:
0
result:
wrong answer 1st lines differ - expected: '3486784401', found: '0'