oj.uz

Submission #433727

# Submission time Handle Problem Language Result Execution time Memory
433727 2021-06-20T10:01:03 Z LouayFarah Traffickers (RMI18_traffickers) C++14
15 / 100
 3500 ms 11848 KB 
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second

#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const ll MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const ll MX = 1e9 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define debug(x) cerr << #x << " : " << x << endl;
#define debugs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define debugv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

vector<ll> create_path(vector<ll> adj[], ll n, ll s, ll e)
{
    vector<bool> visited(n+1, false);
    queue<ll> q;
    vector<ll> parent(n+1, -1);

    bool flag = true;
    visited[s] = true;
    q.push(s);

    while(!q.empty()&&flag)
    {
        ll u = q.front();
        q.pop();

        for(auto v: adj[u])
        {
            if(visited[v])
                continue;
            visited[v] = true;
            parent[v] = u;
            q.push(v);
            if(v==e)
                flag = false;
        }
    }

    vector<ll> path;
    ll x = e;
    while(x!=-1)
    {
        path.pb(x);
        x = parent[x];
    }

    reverse(all(path));
    return path;

    return parent;
}

int main()
{
    boost;
    IO();

    ll n;
    cin >> n;

    vector<ll> adj[n+1];
    ll u, v;
    FOR(i, 0, n-1)
    {
        cin >> u >> v;

        adj[u].pb(v);
        adj[v].pb(u);

    }

    ll k;
    cin >> k;

    vector<pair<ll, ll>> traffickers;
    FOR(i, 0, k)
    {
        cin >> u >> v;
        traffickers.pb(mp(u, v));
    }

    vector<vector<ll>> path(k);
    FOR(i, 0, k)
    {
        path[i] = create_path(adj, n, traffickers[i].fi, traffickers[i].se);
    }

    ll q;
    cin >> q;
    while(q--)
    {
        ll c, s, e, t1, t2;
        cin >> c;
        if(c==1)
        {
            cin >> s >> e;
            traffickers.pb(mp(s, e));
            path.pb(create_path(adj, n, s, e));
            k++;
        }
        if(c==2)
        {
            cin >> s >> e;
            auto ind = find(all(traffickers), mp(s, e));
            traffickers.erase(ind);
            int indd = ind - traffickers.begin();
            path.erase(path.begin() + indd);
            k--;
        }
        if(c==3)
        {
            cin >> s >> e >> t1 >> t2;

            vector<ll> path_marchandise = create_path(adj, n, s, e);

            sort(all(path_marchandise));
            ll res = 0;
            FOR(i, 0, k)
            {
                vector<ll> p = path[i];
                ll len = (ll)p.size();
                ll ptr = 0;
                ptr = t1%len;
                ll timer = t1;
                while(timer<=t2)
                {
                    if(binary_search(all(path_marchandise), p[ptr]))
                        res++;
                    ptr++, timer++;
                    if(ptr==len)
                        ptr = 0;
                }
            }
            cout << res << endl;
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 95 ms 504 KB Output is correct
3 Correct 62 ms 504 KB Output is correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3535 ms 2140 KB Time limit exceeded
2 Execution timed out 3549 ms 2116 KB Time limit exceeded
3 Execution timed out 3580 ms 1916 KB Time limit exceeded
4 Execution timed out 3562 ms 2192 KB Time limit exceeded
5 Execution timed out 3582 ms 2112 KB Time limit exceeded
6 Execution timed out 3582 ms 2184 KB Time limit exceeded
7 Execution timed out 3589 ms 2156 KB Time limit exceeded
8 Execution timed out 3586 ms 2008 KB Time limit exceeded
9 Execution timed out 3584 ms 2220 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3574 ms 11252 KB Time limit exceeded
2 Execution timed out 3595 ms 11068 KB Time limit exceeded
3 Execution timed out 3578 ms 11424 KB Time limit exceeded
4 Execution timed out 3584 ms 11848 KB Time limit exceeded
5 Execution timed out 3577 ms 10360 KB Time limit exceeded
6 Execution timed out 3583 ms 10980 KB Time limit exceeded
7 Execution timed out 3569 ms 10896 KB Time limit exceeded
8 Execution timed out 3599 ms 10872 KB Time limit exceeded