제출 #1281854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281854		ghammazhassan	Two Currencies (JOI23_currencies)	C++20	0 / 100	3 ms	980 KiB

currencies

// #include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
using namespace std;
// #define int long long
#define endl "\n"
#define fi first
#define se second
const int M=1e9+7;
const int inf = 1e9;
const int LOG=20;
const int N=1e5+5;
int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r;
vector<int>a[N];
int p[N];
void solve()
{       
    cin >> n >> m >> q;
    map<pair<int,int>,int>d;
    for (int i=1;i<n;i++){
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
        d[{x,y}]=i;
        d[{y,x}]=i;
    }
    p[1]=1;
    queue<int>o;
    vector<int>vi(n+1);
    vector<int>di(n+1);
    o.push(1);
    vi[1]=1;
    while(o.size()){
        int h=o.front();
        o.pop();
        for (int i:a[h]){
            if (vi[i])continue;
            vi[i]=1;
            di[i]=di[h]+1;
            o.push(i);
            p[i]=h;
        }
    }
    if (n<=2000 and m<=2000 and q<=2000){
        vector<vector<int>>ch(n);
        for (int i=0;i<m;i++){
            cin >> x >> y;
            ch[x].push_back(y);
        }
        for (int i=0;i<q;i++){
            int g,s;
            cin >> x >> y >> g >> s;
            vector<int>l;
            while (x!=y){
                if (di[x]<di[y]){
                    swap(x,y);
                }
                for (int k:ch[d[{x,p[x]}]]){
                    l.push_back(k);
                }
                x=p[x];
            }
            sort(l.begin(),l.end());
            for (int j:l){
                if (j<=s){
                    s-=j;
                }
                else{
                    g--;
                }
            }
            cout << max(-1,g) << endl;
        }
    }
}
signed main()    
{

    ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    cin.tie(0), cout.tie(0);//DO NOT USE IN INTERACTIVE
    cout << fixed << setprecision(9);
    srand(time(0));
    // int t=1;
    // cin >> t;
    for (int _=1;_<=t;_++){
        solve();
        q++;
    }
} 

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32