Submission #1231369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231369		sitingfake	Toll (BOI17_toll)	C++20	7 / 100	253 ms	12776 KiB

toll

#include<bits/stdc++.h>
using namespace std;

// define

#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ld double
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) (((x)>>(i))&1LL)
#define flip(x,i) ((x)^(1LL<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1
#define visit visited
#define left __left
#define right __right

//constant

const ll mod = 1e9 + 7;
const long long linf = 4557430888798830399;
const int inf = 1061109567;
const int maxarr = 1e6 + 5;
int dx[] = {0 , -1 , 0 , 1};
int dy[] = {-1 , 0 , 1 , 0};

template<typename T> bool maximize(T &a, const T &b)
{
    if(a < b) {a = b; return 1;}
    return 0;
}

template<typename T> bool minimize(T &a, const T &b)
{
    if(a > b) {a = b; return 1;}
    return 0;
}

inline void Plus(ll & a ,ll b)
{
    b %= mod;
    a += b;
    if(a >= mod) a -= mod;
    if(a < 0) a += mod;
    return;
}

inline void Mul(ll & a, ll b)
{
    a %= mod; b %= mod;
    a *= b;
    a %= mod;
    return;
}

//code
const int maxn = 5e4 + 7;

vector <ii> a[maxn] , arev[maxn];

int n , m , q , k;

int ans[maxn] , mask[maxn];

int id[20][maxn] , timer[20];

vector <ii> pos[20];

vector <int> dist1 , dist2;

struct query
{
    int l , r;
    int id;
};

vector <vector<query>> Q[20];

void Init(int l , int r , int lv)
{
    if(l > r) return;
    if(l == r) return;
    int mid = (r + l) >> 1;

    pos[lv].push_back(ii(mid , timer[lv]));
    id[lv][mid] = timer[lv];
    timer[lv]++;

    for(int i = mid + 1; i <= r; i++)
    {
        mask[i] |= (1 << lv);
    }

    Init(l , mid , lv + 1);

    Init(mid + 1, r , lv + 1);
}

void dij(int l , int r ,vector <int> &dist , int s , bool f)
{
    for(int i = l ; i <= r; i++) dist[i] = inf;

    dist[s] = 0;

    priority_queue <ii , vector <ii> , greater<ii>> q;

    q.push(ii(0 , s));

    while(!q.empty())
    {
        int u = q.top().se;
        int cost = q.top().fi;
        q.pop();
        if(cost > dist[u]) continue;

        if(f)
        {
            for(ii i : a[u])
            {
                int v = i.fi;
                int w = i.se;
                if(v < l || v > r) continue;
                if(minimize(dist[v] , dist[u] + w))
                {
                    q.push(ii(dist[v] , v));
                }
            }
        }
        else
        {
            for(ii i : arev[u])
            {
                int v = i.fi;
                int w = i.se;
                if(v < l || v > r) continue;
                if(minimize(dist[v] , dist[u] + w))
                {
                    q.push(ii(dist[v] , v));
                }
            }
        }
    }

}

void DnC(int l , int r , int lv)
{
    if(l > r) return;
    if(l == r)
    {
        return;
    }

    int mid = (r + l) >> 1;

    int pos = mid;

    while(pos <= r && abs((pos / k) - (mid / k)) <= 1)
    {
        dij(l , pos , dist1 , pos , 0);
        dij(pos , r , dist2 , pos , 1);

        for(query i : Q[lv][id[lv][mid]])
        {
            if(i.l <= pos && pos <= i.r)
            {
                minimize(ans[i.id] , dist1[i.l] + dist2[i.r]);
            }
        }
        pos++;
    }

    DnC(l , mid , lv + 1);
    DnC(mid + 1, r , lv + 1);
}
void solve(void)
{
    cin >> k >> n >> m >> q;

    for(int i = 1; i <= m; i++)
    {
        int u , v , w;
        cin >> u >> v >> w;
        u++;
        v++;
        a[u].push_back(ii(v , w));
        arev[v].push_back(ii(u , w));
    }

    Init(1 , n , 0);

    for(int i = 0; i <= 19; i++)
    {
        Q[i].resize(timer[i] + 2);
        sort(all(pos[i]));

//        cout << i << endl;
//
//        for(ii i : pos[i])
//        {
//            cout << i.fi << " " << i.se << endl;
//        }
//
//        cout << endl;
    }

    for(int i = 1; i <= q; i++)
    {
        int u , v;
        cin >> u >> v;
        u++;
        v++;

        if(u < v)
        {
            int b = __builtin_ctz(mask[u] ^ mask[v]);

            ii tmp = *(lower_bound(all(pos[b]) , ii(u , 0)));

            if(tmp.fi < v)
            {
                Q[b][tmp.se].push_back({u , v , i});
            }
        }
        else if(u == v)
        {
            ans[i] = 0;
        }
    }

    dist1 = dist2 = vector <int> (n + 2 , inf);
    ms(ans , 0x3f);

    DnC(1 , n , 0);

    for(int i = 1; i <= q; i++)
    {
        if(ans[i] == inf)
        {
            cout << "-1\n";
        }
        else cout << ans[i] << "\n";
    }

}
/**
**/
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);

   #define task ""

   if(fopen(task".inp","r"))
   {
       freopen(task".inp","r",stdin);
       freopen(task".out","w",stdout);
   }

   int tc; tc = 1;

   while(tc--) solve();

   //execute;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:263:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  263 |        freopen(task".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:264:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  264 |        freopen(task".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44