Submission #433985

#	Time	Username	Problem	Language	Result	Execution time	Memory
433985		AmineTrabelsi	Traffickers (RMI18_traffickers)	C++14	0 / 100	1123 ms	640 KiB

traffickers

#include "bits/stdc++.h"
using namespace std;
// Hi 
int n;
vector<int> gr[5005];
set<pair<int,int>> traf;
vector<int> path;
void dfs(int u,int par,int v){
    if(u == v){
        path.push_back(v);
        return;
    }
    for(auto i:gr[u]){
        if(i != par){
            dfs(i,u,v);
            if(!path.empty())break;
        }
    }
    if(!path.empty())path.push_back(u);
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        x--,y--;
        gr[x].push_back(y);
        gr[y].push_back(x);
    }
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        int x,y;
        cin>>x>>y;
        x--,y--;
        traf.insert({x,y});
    }
    int q;
    cin>>q;
    while(q--){
        int t;
        cin>>t;
        if(t == 1){
            int x,y;
            cin>>x>>y;
            x--,y--;
            traf.insert({x,y});
        }else if(t == 2){
            int x,y;
            cin>>x>>y;
            x--,y--;
            traf.erase({x,y});
        }else{
            int x,y,l,r;
            cin>>x>>y>>l>>r;
            x--,y--;
            vector<int> cnt(n+1,0);
            for(auto i:traf){
                path.clear();
                dfs(i.first,-1,i.second);
                reverse(path.begin(),path.end());
                /*
                for(auto pp:path)cout << pp <<" ";
                    cout << '\n';*/
                int pos = 0;
                int p = path.size();
                for(int xx=0;xx<=r;xx++){
                    if(xx>=l)cnt[path[pos]]++;
                    if(pos == p-1)pos = 0;
                    else pos++;
                }
            }
            path.clear();
            dfs(x,-1,y);
            reverse(path.begin(),path.end());
            int ans = 0;
            for(auto i:path)ans += cnt[i];
                cout << ans << '\n';
        }
    }
    return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40