Submission #433919

#	Time	Username	Problem	Language	Result	Execution time	Memory
433919		HediChehaidar	Traffickers (RMI18_traffickers)	C++17	0 / 100	123 ms	49056 KiB

traffickers

/*
ID: hedichehaidar
TASK: photo
LANG: C++11
*/
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define dte  tuple<double , double , double>
using namespace std;
const int INF = 1000*1000*1000; // 1 e 9
const int MOD = INF + 7;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;

int n , q , k , t1 , t2;
int ans;
vi adj[1010];
vi path[1010][1010];
set<int> p;
set<pii> s;
vi v;
int d , e;
void dfs(int pos , int par){
    v.pb(pos);
    if(pos == e){
        path[d][e] = v;
        v.pop_back(); return;
    }
    for(auto c : adj[pos]){
        if(c != par) dfs(c , pos);
    }
    v.pop_back();
}
int main() {
    //ifstream fin ("race.in");
    //ofstream fout ("race.out");
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i = 0 ; i < n - 1 ; i++){
        int a , b; cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    cin>>k;
    for(int i = 0 ; i < k ; i++) {
        int a , b; cin>>a>>b;
        s.insert({a , b});
    }
    for(auto c : s){
        if(path[c.ff][c.ss].empty()){
            d = c.ff; e = c.ss; dfs(c.ff , -1);
        }
    }
    cin>>q;
    while(q--){
        int t , a , b; cin>>t>>a>>b;
        if(t == 1){
            s.insert({a , b});
            if(path[a][b].empty()){
                d = a; e = b; dfs(d , -1);
            }
        }
        else if(t == 2){
            s.erase({a , b});
        }
        else{
            cin>>t1>>t2;
            if(path[a][b].empty()){
                d = a; e = b; dfs(d , -1);
            }
            for(auto c : path[a][b]) p.insert(c);
            ans = 0;
            for(auto c : s){
                d = c.ff; e = c.ss;
                int nb = path[d][e].size();
                for(int i = t1 ; i <= t2 ; i++){
                    int pos = path[d][e][i % nb];
                    if(p.find(pos) != p.end()) ans++;
                }
            }
            cout << ans << "\n";
        }
    }
    return 0;
}

/*
    Think of : BS / DFS / BFS / SSSP / SCC / MSP / MAX FLOW / TOPSORT / LCA / MATRIX / DP(bitmask) / 2 POINTERS / SEG TREE / MATH / UN FIND / MO
    Read the statement CAREFULLY !!
    Make a GREADY APPROACH !!!! (start from highest / lowest)
    Make your own TESTS !!
    Be careful from CORNER CASES !
*/

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