oj.uz

Submission #1078687

# Submission time Handle Problem Language Result Execution time Memory
1078687 2024-08-28T04:27:23 Z _rain_ Robot (JOI21_ho_t4) C++14
0 / 100
 376 ms 21256 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fixbug false

void SETIO(string name = ""){
    if (name=="") return;
    freopen((name+".inp").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
    return;
}

const int maxn = 1e5;
const int maxm = 2e5;
const ll INF = (ll)1e18+7;
struct _data{
    ll cost; int u , color;
    bool operator > (const _data &other) const{
        return cost > other.cost;
    }
    bool operator < (const _data &other) const{
        return cost < other.cost;
    }
};
struct Node{
    int to , c , p;
};
vector<Node> g[maxn+2];
ll sum[maxm+2];
bool used[maxn+2] = {};
map<pair<int,int> , bool> vis;
int n , m;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    SETIO("");

    cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int u , v , c , p;
        cin >> u >> v >> c >> p;
        g[u].push_back({v , c , p});
        g[v].push_back({u , c , p});
    }
    //... build the base
    priority_queue<_data,vector<_data>,greater<_data>> q;
    ll ans = INF;
    q.push({0 , 1 , m + 1});
    while (q.size()){
    	ll cost = q.top().cost;
    	int u = q.top().u;
    	int color = q.top().color;
    	q.pop();
    	
    	if (vis[{u , color}] == 1) continue;
    	if (fixbug){
    		cout << "(DEBUG)\n";
    		cout << u << ' ' << color << ' ' << cost << '\n';
    	}
    	vis[{u , color}] = true;
    	if (u == n) ans = min(ans , cost);
    	for (auto& x : g[u])
    		sum[x.c] += x.p;    	
    	for (auto& x : g[u]){
    		int v = x.to , c = x.c , p = x.p;
    		if (c == color) continue;
    		if (!vis[{v , m + 1}]) q.push({cost + p , v , m + 1});
    		if (!vis[{v , c}]) q.push({cost + sum[c] - p , v , c});
    		if (fixbug){
	    		cout << "(DEBUG ORZZZ)\n";
	    		cout << u << "->" << v << ' ' << c << ' ' << sum[c] << '\n';
	    		cout << '\n';
    		}
    	}
    	for (auto& x : g[u])
    		sum[x.c] -= x.p;
    }
    cout << ans;
}

Compilation message

Main.cpp: In function 'void SETIO(std::string)':
Main.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen((name+".inp").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 16708 KB Output is correct
2 Correct 118 ms 9388 KB Output is correct
3 Correct 376 ms 21256 KB Output is correct
4 Incorrect 147 ms 11708 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -