oj.uz

Submission #218196

# Submission time Handle Problem Language Result Execution time Memory
218196 2020-04-01T13:20:35 Z 1254141856 Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 1000 ms 1912 KB 
/* 
    
*/ 
#include <bits/stdc++.h>
#define md(x, y)  (x + y) / 2
#define ls(x)      x << 1
#define rs(x)      x << 1 | 1
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;

const int MAXN = 2e2 + 10;
int cnt, head[MAXN], vis[MAXN];
int mp[MAXN][MAXN], cost[MAXN][MAXN];
ll yen, ans;
int n, m, uu, tt;
struct Edge
{
    int v, next;
}edge[50010];
void add(int u, int v)
{
    cnt++;
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

void dfs(int u, int fa, int s)
{
    if(u == tt) s = 1;
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].v;
        if(v == fa || vis[v]) continue;
        yen += mp[u][v];
        vis[v] = true;
        dfs(v, u, s);
        yen -= mp[u][v];
        vis[v] = false;
    }
    if(s)
    {
        if(mp[u][uu] < INF)  ans = min(ans, yen + mp[u][uu]);
        if(mp[uu][u] < INF && uu != fa) ans = min(ans, yen + mp[uu][u] + cost[uu][u]);
    }
}
int main()
{
    cin >> n >> m;
    memset(head, -1, sizeof head);
    memset(mp, INF, sizeof mp);
    memset(cost, INF, sizeof cost);
    for(int i = 1; i <= m; i++)
    {
        int u, v, c, d;
        scanf("%d%d%d%d", &u, &v, &c, &d);
        mp[u][v] = min(c, mp[u][v]);        
        cost[u][v] = min(cost[u][v], d);
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(mp[i][j] < INF)  add(i, j);
    ans = 1e18;
    //printf("ans - %lld\n", ans);
    yen = 0;
    uu = 1;
    tt = n;
    vis[1] = true;
    dfs(1, 1, 0);
    memset(vis, false, sizeof vis);
    vis[n] = true;
    tt = 1;
    uu = n;
    yen = 0;
    dfs(n, n, 0);
    if(ans >= 1e18)  printf("-1\n");
    else            printf("%lld\n", ans);
    
    return 0;
}

Compilation message

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &u, &v, &c, &d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 1912 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 640 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 768 KB Time limit exceeded
2 Halted 0 ms 0 KB -