oj.uz

답안 #573953

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
573953 2022-06-07T13:27:24 Z PedroBigMan Sky Walking (IOI19_walk) C++14
0 / 100
 4000 ms 701980 KB 
/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "walk.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

class WG //everything works for weighted directed graphs except dynamic graph
{
    public:
    ll N; vector<vector<pl> > adj;
    vector<bool> pr; 
    
    WG(vector<vector<pl> > ad)
    {
        adj=ad; N=adj.size();
        REP(i,0,N) {pr.pb(false);}
    }
    
    vector<ll> Dijkstra(ll s)
    {
        vector<ll> d; REP(i,0,N) {d.pb(INF);}
        d[s]=0;
        priority_queue<pl> q;
        q.push(mp(0,s));
        ll cur;
        while(!q.empty())
        {
            cur=q.top().ss; q.pop();
            if(pr[cur]) {continue;}
            pr[cur]=true; 
            REP(i,0,adj[cur].size())
            {
                if(d[adj[cur][i].ff]>d[cur]+adj[cur][i].ss)
                {
                    d[adj[cur][i].ff]=d[cur]+adj[cur][i].ss;
                    q.push(mp(-d[adj[cur][i].ff],adj[cur][i].ff));
                }
            }
        }
        return d;
	}
};

ll min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) 
{
	ll N = x.size(); ll M = l.size();
	vector<vector<ll> > be,en; VV(be,N,{}); VV(en,N,{});
	REP(i,0,M) {be[l[i]].pb(i); en[r[i]].pb(i);}
	multiset<ll> active; multiset<ll>::iterator it; active.insert(0);
	vector<pl> p; 
	vector<vector<ll> > inter; 
	vector<ll> fir;
	REP(i,0,N)
	{
		fir.pb(p.size());
		REP(j,0,be[i].size()) 
		{
			active.insert(y[be[i][j]]);
		}
		it=active.begin(); 
		while(it!=active.end() && *it <= h[i])
		{
			p.pb({x[i],*it});
			it++;
		}
		REP(j,0,en[i].size()) 
		{
			active.erase(active.find(y[en[i][j]]));
		}
	}
	ll P = p.size(); vector<vector<pl> > adj; VV(adj,P,{}); ll we;
	REP(i,0,P-1)
	{
		if(p[i+1].ff==p[i].ff) {we=p[i+1].ss-p[i].ss; adj[i].pb({i+1,we}); adj[i+1].pb({i,we});}
	}
	map<ll,vector<ll> > m;
	REP(i,0,P) 
	{
		if(m.find(p[i].ss)==m.end()) {m[p[i].ss]={};}
		m[p[i].ss].pb(i);
	}
	map<ll,vector<ll> >::iterator it2; ll ind1,ind2;
	REP(i,0,M)
	{
		ll j = (ll) (lower_bound(whole(m[y[i]]),fir[l[i]]) - m[y[i]].begin());
		it2=m.find(y[i]);
		while(1>0)
		{
			ind1=it2->ss[j]; ind2=it2->ss[j+1]; we=p[ind2].ff-p[ind1].ff;
			adj[ind1].pb({ind2,we}); adj[ind2].pb({ind1,we});
			if(p[ind2].ff==x[r[i]]) {break;}
			j++;
		}
	}
	
	ll A = (ll) (find(whole(p),(pl){x[s],0}) - p.begin());
	ll B = (ll) (find(whole(p),(pl){x[g],0}) - p.begin());
	//REP(i,0,P) {cout<<i<<" "<<p[i].ff<<" "<<p[i].ss<<endl;}
	//REP(i,0,P) {cout<<i<<endl;REP(j,0,adj[i].size()) {cout<<adj[i][j].ff<<" "<<adj[i][j].ss<<endl;}} 
	WG G(adj);
	vector<ll> d = G.Dijkstra(A); 
	//REP(i,0,P) {cout<<p[i].ff<<" "<<p[i].ss<<" "<<d[i]<<endl;}
	return d[B];
}

Compilation message

walk.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
walk.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1215 ms 250920 KB Output is correct
4 Correct 1267 ms 272272 KB Output is correct
5 Correct 872 ms 234964 KB Output is correct
6 Correct 826 ms 208228 KB Output is correct
7 Incorrect 857 ms 235220 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 42432 KB Output is correct
2 Execution timed out 4100 ms 701980 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 42432 KB Output is correct
2 Execution timed out 4100 ms 701980 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -