Submission #851739

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
851739	2023-09-20T14:02:07 Z	fcmalkcin	Alias (COCI21_alias)	C++17	70 / 70	50 ms	4176 KB

alias

#include<bits/stdc++.h>

using namespace std;


#define pb  push_back
#define ll  long long
#define pll pair<ll,ll>
#define ff  first
#define ss  second
#define endl "\n"
const ll maxn=1e5+54;
const ll mod =998244353   ;
const ll base=3e18;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


ll cnt;
map<string, ll> ind_map;

ll ind(string x) {
    if (ind_map.find(x) == ind_map.end())
        ind_map[x] = cnt++;
    return ind_map[x];
}

ll n, m, q;
vector<pll> e[maxn];

ll dist[maxn];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("guard.in", "r"))
    {
        freopen("guard.in", "r", stdin);
        freopen("guard.out", "w", stdout);
    }
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        ll t;
        string x, y;
        cin >> x >> y >> t;
        e[ind(x)].push_back(make_pair(ind(y), t));
    }
    cin >> q;
    for (ll i = 0; i < q; i++) {
        string x, y;
        cin >> x >> y;
        set<pll> s;
        memset(dist, -1, sizeof dist);
        dist[ind(x)] = 0;
        s.insert(pll(0ll, ind(x)));
        while (!s.empty()) {
            pll curr = *s.begin();
            s.erase(curr);
            ll curr_ind = curr.second;
            for (ll j = 0; j < (ll)e[curr_ind].size(); j++) {
                ll nxt = e[curr_ind][j].first;
                ll d = e[curr_ind][j].second;
                if (dist[nxt] == -1 || dist[nxt] > dist[curr_ind] + d) {
                    s.erase(pll(dist[nxt], nxt));
                    dist[nxt] = dist[curr_ind] + d;
                    s.insert(pll(dist[nxt], nxt));
                }
            }
        }
        if (dist[ind(y)] == -1)
            cout << "Roger" << endl;
        else
            cout << dist[ind(y)] << endl;
    }
    return 0;
}
/*
5 1
1 2
4
+ 1
?
+ 1
?
*/

Compilation message

alias.cpp: In function 'int main()':
alias.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen("guard.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
alias.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen("guard.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	3416 KB	Output is correct
2	Correct	2 ms	3416 KB	Output is correct
3	Correct	41 ms	3684 KB	Output is correct
4	Correct	50 ms	3700 KB	Output is correct
5	Correct	16 ms	4176 KB	Output is correct
6	Correct	15 ms	3672 KB	Output is correct
7	Correct	18 ms	3672 KB	Output is correct