Submission #1015699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015699		Taresu	Robot (JOI21_ho_t4)	C++11	0 / 100	532 ms	51544 KiB

Main

#include <bits/stdc++.h>
     
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
         
    #define INF 0x7fffffff
    #define MINF -0x7fffffff
    #define MAX_VAL 0x7fffffffffffffff
    #define pb push_back
    #define sz(a) a.size()
    #define mod 998244353
    #define MOD 1000000007
    #define f first
    #define s second   
    #define sortv(a) sort(a.begin(), a.end())
    #define rsortv(a) sort(a.rbegin(), a.rend())
    #define ins insert
    #define fr(i, a) for(long long int i=0;i<a;i++)
    #define fr1(i, a) for(long long int i=1;i<=a;i++)
    #define mem0(a) memset(a, 0, sizeof(a)) // a nome da matirz
    #define mem1(a) memset(a, 1, sizeof(a))
    #define mem_1(a) memset(a, -1, sizeof(a))
    #define memI(a) memset(a, 0x3f3f3f3f, sizeof(a))
    #define formap(it, a) for(map<pipii, ll>::iterator it=a.begin();it!=a.end();it++)
    #define forset(it, a) for(set<int>::iterator it=a.begin();it!=a.end();it++)
    #define formset(it, a) for(multiset<int>::iterator it=a.begin();it!=a.end();it++)
 
    using namespace std;   
    using namespace __gnu_pbds;
     
    typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>ordered_set;
     
    typedef long long int ll;
    typedef pair<ll, ll> pii;
    typedef pair<ll, pair<ll, ll> > pipii;
    typedef priority_queue<pipii, vector<pipii>, greater<pipii> > pqueue;

    using Matrix = array<array<ll, 110>, 110>;

    Matrix mul(Matrix a, Matrix b, ll m){
	    Matrix res;
        fr(i, 110)
            fr(j, 110)
                res[i][j]=0x3f3f3f3f3f3f3f3f;

	    for (int i = 1; i < 101; i++) {
		    for (int j = 1; j < 101; j++) {
			    for (int k = 1; k < 101; k++) {
                    //res[i][j] += a[i][k] * b[k][j]; // multiplicaçao
				    //res[i][j] = min(res[i][j], a[i][k] + b[k][j]); // min sum distance
				    //res[i][j] %= m;
			}
		}
	}
	    return res;
    }
 
    ll gcd(ll a, ll b){
        return b==0 ? a : gcd(b, a%b); 
    }
    ll lcm(ll a, ll b){
        return (a*b)/gcd(a, b); 
    }
    ll fexp(ll b, ll e, ll m){
        if(e==0) return 1;
        if(e==1) return b%m;
 
        ll h=fexp(b, e/2, m);
        if(e%2==0){
            return (h*h)%m;
        }else{
            return (((h*h)%m)*b)%m;
        }
    }
    Matrix indentityMatrix(int n){
        Matrix id;
        fr(i, n){
            fr(j, n){
                id[i][j]=0;
                if(i==j)
                    id[i][j]=0x3f3f3f3f3f3f3f3f; // se for so multilicaçao 1 se min dist coloque o infinito
            }
        }
        return id;
    }
    Matrix mexp(Matrix b, ll e, ll m){
        if(e==0) return indentityMatrix(101); // a dependennder da operaçao mul a identidade mdua
        if(e==1) return b;
 
        Matrix h=mexp(b, e/2, m);
        if(e%2==0){
            return mul(h, h, m);
        }else{
            return mul(mul(h, h, m), b, m);
        }
    }
    ll inv(ll x, ll m){
	    if (x <= 1) {
             return x;
        }
	    return m-m/x*inv(m % x, m)%m;
    }
    void irr(ll *a, ll *b){ //deixar primos entre si
        ll gc=gcd(*a, *b);
        *a/=gc;
        *b/=gc;
    }
    ll divmod(ll num, ll den, ll m){
        return (num*fexp(den, m-2, m))%m;
    }
    int setbits(int x){
        return __builtin_popcount(x);
    }
    int lgb(ll x, ll b){
        int ct=-1;
        while(x>0){
            ct++;
            x/=b;
        }
        return ct+1;
    }

    struct vetor{
        double x, y;
    };

     double norma(vetor a){
        return sqrt(a.x*a.x+a.y*a.y);
    }

    double dotproduct(vetor a, vetor b){
        return a.x*b.x+a.y*b.y;
    }

    double arg(vetor a, vetor b){
        double ag=dotproduct(a, b)/(norma(a)*norma(b));
        return -1*acos(ag);
    }

    vetor rotacionaarg(vetor v, double ang){
        vetor r={v.x*cos(ang)-v.y*sin(ang), v.y*cos(ang)+v.x*sin(ang)};
        return r;
    }
 
    ///////////////SOLVE
    //////////////////////////////////
    ////////////////////////

     
    vector<pipii> g[100100];
    ll dist[100100];
    ll cordp[200100];
    map<ll, multiset<ll> > cores;
    bool processado[100100];

    bool onlyone(ll v, ll cor){
        bool ans=0;
        cores[v].erase(cores[v].find(cor));
        if(cores[v].find(cor)==cores[v].end())
            ans=1;
        cores[v].ins(cor);
        return ans;
    }

    void solve(){
        memset(processado, 0, sizeof(processado));
        fr(i, 100100){
            dist[i]=0x3f3f3f3f3f3f3f3f;
        }
       int n;

       cin >> n;

       int q;

       cin >> q;

       for(int i=0;i<q;i++){
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        g[a].push_back({b, {d, i}});
        g[b].push_back({a, {d, i}});
        cores[a].ins(c);
        cores[b].ins(c);
        cordp[i]=c;
       }

       // djikstra begin
       dist[1]=0;
       priority_queue<pii, vector<pii>, greater<pii> > fila;
       fila.push({0, 1});

        while(true){
            int davez=-1;

            while(!fila.empty()){
                int u=fila.top().s;
                fila.pop();
                if(!processado[u]){
                    processado[u]=1;
                    davez=u;
                    break;
                }
            }

            if(davez==-1){
                break;
            }

            for(int i=0;i<sz(g[davez]);i++){
                int olho=g[davez][i].f;
                int peso=g[davez][i].s.f;
                int pista=g[davez][i].s.s;

                if(onlyone(davez, cordp[pista]))
                    peso=0;

                if(dist[olho]>dist[davez]+peso){
                    dist[olho]=dist[davez]+peso;
                    fila.push({dist[olho], olho});
                }
            }
        }

        if(dist[n]==0x3f3f3f3f3f3f3f3f) cout << "-1\n";
        else cout << dist[n] << '\n';
       //djikstra end
    }

 
    ///////////////SOLVE
    //////////////////////////////////
    ////////////////////////
    
    int32_t main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        
        /*/freopen("mootube.in","r",stdin);
	    freopen("mootube.out","w",stdout);/**/
        int t=1;
        //cin >> t;
        
        while(t--){
            solve();
        }
 
        return 0;
     }

Compilation message (stderr)

Main.cpp:240:40: warning: "/*" within comment [-Wcomment]
  240 |      freopen("mootube.out","w",stdout);/**/
      |                                         
Main.cpp: In function 'void solve()':
Main.cpp:210:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |             for(int i=0;i<sz(g[davez]);i++){
      |                          ^

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