Submission #1176685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176685		paulxaxa	Robot (JOI21_ho_t4)	C++17	0 / 100	3096 ms	18880 KiB

Main

#include <bits/stdc++.h>

#define NMAX 100000
#define LOG 20

#define ll long long int
#define BASE 32

#define MOD 1000000007


using namespace std;

ifstream fin("cod.in");
ofstream fout("cod.out");

int n,m;
struct edge
{
    int to,c,p,id;
};
struct state
{
    ll d;
    int x,t;
    state(ll d,int x,int t)
    {
        this->d = d;
        this->x = x;
        this->t = t;
    }
};
bool cmpHeap(state a,state b)
{
    return a.d > b.d;
}

vector<edge> adj[NMAX+1];

set<int> bad[NMAX+1];
int rem[NMAX+1];
ll dist[NMAX+1][2];


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c,p;
        cin >> a >> b >> c >> p;
        adj[a].push_back({b,c,p,i});
        adj[b].push_back({a,c,p,i});
    }

    for(int i=1;i<=n;i++)
    {
        map<int,int> freq;
        for(auto e : adj[i])
        {
            if(freq[e.c] > 0)
            {
                rem[i]++;
            }
            freq[e.c]++;
        }
        for(auto e : adj[i])
        {
            if(freq[e.c]>1)
            {
                bad[i].insert(e.id);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        dist[i][0] = dist[i][1] = 1e15;
    }
    vector<state> pq;
    dist[1][0] = 0;
    pq.push_back({0,1,0});
    while(!pq.empty())
    {
        push_heap(pq.begin(),pq.end(),cmpHeap);
        int x = pq.back().x;
        int t = pq.back().t;
        ll d = pq.back().d;
        pq.pop_back();

        if(d==dist[x][t])
        {
            int cost = rem[x] - t;
            for(auto e : adj[x])
            {
                int t1 = bad[e.to].find(e.id) != bad[e.to].end();
                if(dist[e.to][t1] > dist[x][t] + cost)
                {
                    dist[e.to][t1] = dist[x][t] + cost;
                    pq.push_back({dist[e.to][t1],e.to,t1});
                    push_heap(pq.begin(),pq.end(),cmpHeap);
                }
            }
        }
    }
    cout << min(dist[n][0],dist[n][1]);

}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42