oj.uz

답안 #990867

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
990867 2024-05-31T15:21:51 Z Requiem 악어의 지하 도시 (IOI11_crocodile) C++17
0 / 100
 2000 ms 35420 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
//#define ll long long
#define ll long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(ll i=a;i<=b;i++)
#define FORD(i,a,b) for(ll i=a;i>=b;i--)
#define sz(a) ((ll)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "crocodile"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<ll,ll> ii;
typedef pair<ll,ii> iii;
typedef vector<ll> vi;

const ll MAXN = 3e5 + 9;
ll n, m, k;
vector<ll> g[MAXN], exitVertice;
iii edge[MAXN];
ll deg[MAXN], isExit[MAXN], special[MAXN], bad[MAXN];
ll NumNode, NumEdge, NumCmp = 0;

set<ii> optimal[MAXN];

namespace subtask2{
    bool checkSubtask2(){
         return n <= 1000 and m <= 100000;
    }
    long long dist[1003][1003];

    void dijkstra(ll s){
         memset(dist[s], 0x3f, sizeof(dist[s]));
         priority_queue<ii, vector<ii>, greater<ii>> pq;
         pq.push({0, s});
         dist[s][s] = 0;
         while(!pq.empty()){
               ll du = pq.top().fi;
               ll u = pq.top().se;

//               cout << u << ' ' << du << endl;
               pq.pop();

               for(auto id: g[u]){
                   ll v = edge[id].se.fi + edge[id].se.se - u;
                   if (minimize(dist[s][v], dist[s][u] + edge[id].fi)){
                       pq.push({dist[s][v], v});
                   }
               }
         }
    }

    ll go(){
         ll cur = 0, prvEdge = -1, ans = 0;
         while(isExit[cur] == 0){
             ll tryed = 0;
//             cerr << cur << ' ';
             while(!optimal[cur].empty()){
                 ll id = (*optimal[cur].begin()).se;
                 tryed++;
//                 cout << (*optimal[cur].begin()).fi << ' ' << cur << ' ' << id << endl;
                 optimal[cur].erase(optimal[cur].begin());

                 if ((id != prvEdge and tryed == 1) or id == prvEdge) continue;

                 cur = edge[id].se.fi + edge[id].se.se - cur;
                 prvEdge = id;
                 ans += edge[id].fi;
//                 cout << "?" << id << ' ' << edge[id].fi << endl;
                 break;
            }
         }
         return ans;
    }
    int solveSubtask2(){

         for(ll i = 1; i < n; i++){
             if (deg[i] == 2 and isExit[i] == 0) bad[i] = true;
         }

//         for(ll i = 0; i < n; i++){
//             cout << bad[i] << ' ';
//         }
//         cout << endl;
         for(ll i = 1; i <= m; i++){
             ll u = edge[i].se.fi;
             ll v = edge[i].se.se;

             if (bad[u] or bad[v]) continue;
             g[u].pb(i);
             g[v].pb(i);
         }


         for(ll i = 0; i < n; i++){
             dijkstra(i);
         }
//         for(ll i = 0; i < n; i++){
//             for(ll j = 0; j < n; j++){
//                 cout << dist[i][j] << ' ';
//             }
//             cout << endl;
//         }
//         cout << endl;

         for(ll i = 1; i <= m; i++){
             ll u = edge[i].se.fi;
             ll v = edge[i].se.se;
             ll w = edge[i].fi;

             if (bad[u] or bad[v]) continue;

//             cout << u << ' ' << v << ' ' << isExit[u] << ' ' <<isExit[v] << endl;
             if (isExit[v]) {
//                 cout << w << ' ' << u << ' ' << v << ' ' << i << endl;
                 optimal[u].insert({w, i});
             }
             if (isExit[u]) optimal[v].insert({w, i});

             for(ll j = 1; j <= k; j++){
                 ll x = exitVertice[j - 1];
                 if (x != v) optimal[u].insert({dist[v][x] + w, i});
                 if (x != u) optimal[v].insert({dist[u][x] + w, i});

                 while(optimal[u].size() > 3) optimal[u].erase(--optimal[u].end());
                 while(optimal[v].size() > 3) optimal[v].erase(--optimal[v].end());
             }
         }
         return go();
//         return 0;
    }

}
int travel_plan(int N, int M, int R[][2], int W[], int K, int E[]){
    n = N, m = M;
    for(ll i = 0; i < m; i++){
        edge[i + 1].fi = W[i];
        deg[R[i][0]]++;
        deg[R[i][1]]++;
        edge[i + 1].se = {R[i][0], R[i][1]};
    }

    k = K;
    for(ll i = 1; i <= k; i++){
        exitVertice.pb(E[i - 1]);
        isExit[E[i - 1]] = true;
    }

    return subtask2::solveSubtask2();
}

/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE

--> Coi lai truoc khi nop
**/

Compilation message

crocodile.cpp: In function 'void subtask2::dijkstra(long long int)':
crocodile.cpp:45:19: warning: unused variable 'du' [-Wunused-variable]
   45 |                ll du = pq.top().fi;
      |                   ^~

Subtask #1
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2062 ms 35420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2062 ms 35420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2062 ms 35420 KB Time limit exceeded
2 Halted 0 ms 0 KB -