Submission #433944

#	Time	Username	Problem	Language	Result	Execution time	Memory
433944		HediChehaidar	Traffickers (RMI18_traffickers)	C++17	15 / 100	175 ms	49076 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;
map<pii , int > m;
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});
        m[{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;
   /* for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++){
            if(path[i][j].empty()){
                d = i; e = j;
                dfs(d , -1);
            }
            cout << i << " " << j << "   ";
            for(auto c : path[i][j]) cout << c << " " ; cout << "\n";
        }
    }*/
    while(q--){
        int t , a , b; cin>>t>>a>>b;
        if(t == 1){
            s.insert({a , b});
            m[{a , b}]++;
            if(path[a][b].empty()){
                d = a; e = b; dfs(d , -1);
            }
        }
        else if(t == 2){
            m[{a , b}]--;
            if(m[{a , b}] == 0)
                s.erase({a , b});
        }
        else{
            cin>>t1>>t2;
            p.clear();
            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){
                int cur = 0;
                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()) cur++;
                }
                ans += cur * m[{c.ff , c.ss}];
            }
            cout << ans << "\n";
        }
    }
    return 0;
}
/*
5
1 2
2 3
2 4
1 5
1
4 1
5
3 3 5 1 20
1 2 5
2 4 1
1 2 5
3 4 5 1 5
*/
/*
    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: 15 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40