QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#56249#1972. JJ RallyAmrMohameDTL 29ms200264kbC++3.0kb2022-10-18 07:52:252022-10-18 07:52:26

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-18 07:52:26]
  • 评测
  • 测评结果:TL
  • 用时:29ms
  • 内存:200264kb
  • [2022-10-18 07:52:25]
  • 提交

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};
int n, m, t,dp[24][M],dp2[24][M], s1,s2,t1,t2,dis[N][N],mp[N];
vector<pi> g[25];
int solve2(int node,int msk)
{
    if(mp[t2] == node){
        return 1;
    }
    int &ret = dp2[node][msk];
    if(~ret)
        return ret;
    ret = 0;
    for(auto it:g[node])
    {
        if(it.ft != mp[s1] && it.ft != mp[t1] && 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;
}
int solve(int node,int msk)
{
    if(mp[t1] == node){
        return solve2(mp[s2],msk);
    }
    int &ret = dp[node][msk];
    if(~ret)
        return ret;
    ret = 0;
    for(auto it:g[node])
    {
        if(it.ft != mp[s2] && it.ft != mp[t2] && 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: 24ms
memory: 200160kb

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: 20ms
memory: 200164kb

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: 29ms
memory: 200264kb

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
Time Limit Exceeded

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:


result: