Submission #1004649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004649		ErJ	Prize (CEOI22_prize)	C++17	0 / 100	3530 ms	174744 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vi vector<ll>
#define pp pair<ll, ll>
#define vp vector<pp>
#define vvi vector<vi>
#define inf 1000000000
#define rep(i,n) for(int i = 0; i < n; i++)

vvi edges, edges2, edges3;
int k;

void dfs(int u, int par, int last){
    if(u < k && (u != last)) {
        edges3[u].push_back(last);
        edges3[last].push_back(u);
        last = u;
    }
    for(int v : edges[u]){
        if(par != v){
            dfs(v, u, last);
        }
    }
}

vector<pp> Itree;

void init(int n){
    while(n & (n-1)) n++;
    Itree.resize(2*n, {inf, inf});
}

void update(int ind, pp val){
    ind += Itree.size() / 2;
    Itree[ind] = val;
    while(ind > 1){
        ind /= 2;
        Itree[ind] = min(Itree[2*ind], Itree[2*ind + 1]);
    }
}

pp get2(ll u, ll l , ll r, ll a, ll b){
    if(l == a && r == b) {
        return Itree[u];
    }
    ll s = (a + b) / 2;
    if(r <= s){
        return get2(2*u, l, r, a, s);
    }else if(l >= s){
        return get2(2*u + 1, l, r, s, b);
    }else{
        return min(get2(2*u, l, s, a, s), get2(2*u + 1, s, r, s, b));
    }
}

pp get(ll l, ll r){
    return get2(1, l, r, 0, Itree.size() / 2);
}


vector<pp> eulerTour;
vi inEuler;

void euler(int u, int par, int hlad){
    inEuler[u] = eulerTour.size();
    for(int v : edges3[u]){
        if(v != par){
            eulerTour.push_back({hlad, u});
            euler(v, u, hlad + 1);
        }
    }
    eulerTour.push_back({hlad, u});
}

ll lca(ll u, ll v){
    return get(min(inEuler[u], inEuler[v]), max(inEuler[u], inEuler[v]) + 1).second;
}

vi dist;
vvi val;

void dfsDist(int u, int par){
    rep(i, edges3[u].size()){
        int v = edges3[u][i];
        if(v != par){
            dist[v] = dist[u] +  val[u][i];
            dfsDist(v, u);
        }
    }
}

ll query(ll u, ll v){
    ll LCA = lca(u, v);
    ll ans = dist[u] + dist[v] - 2*dist[LCA];
    return ans;
}

int main(){
    int n, q, t;
    cin >> n >> k >> q >> t;
    edges.resize(n);
    int root = -1;
    rep(i, n){
        int u;
        cin >> u;
        if(u == -1){
            root = i;
        }else{
            u--;
            edges[u].push_back(i);
            edges[i].push_back(u);
        }
    }
    int root2 = -1;
    edges2.resize(n);
    rep(i, n){
        int u;
        cin >> u;
        if(u == -1){
            root2 = i;
        }else{
            u--;
            edges2[u].push_back(i);
            edges2[i].push_back(u);
        }
    }
    edges3.resize(k);
    dfs(0, -1, 0);
    vp quest;
    val.resize(k);
    rep(i, edges3.size()){
        val[i].resize(edges3[i].size());
        rep(j, edges3[i].size()){
            int u = edges3[i][j];
            if(i < u){
                quest.push_back({i, j});
                cout << "? " << i + 1 << " " << u + 1 << endl;
            }
        }
    }
    cout << "!" << endl;
    cout.flush();
    inEuler.resize(k);
    euler(0, -1, 0);
    init(eulerTour.size());
    rep(i, eulerTour.size()){
        update(i, eulerTour[i]);
    }
    
    rep(i, k - 1){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        val[quest[i].first][quest[i].second] = a + b;
    }
    dist.resize(k, 0);
    dfsDist(0, -1);
    rep(i, t){
        int u, v;
        cin >> u >> v;
        u--; v--;
        ll ans = query(u, v);
        cout << ans << " "<< ans << endl;
    }
}

Compilation message (stderr)

Main.cpp: In function 'void dfsDist(int, int)':
Main.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define rep(i,n) for(int i = 0; i < n; i++)
......
   86 |     rep(i, edges3[u].size()){
      |         ~~~~~~~~~~~~~~~~~~~        
Main.cpp:86:5: note: in expansion of macro 'rep'
   86 |     rep(i, edges3[u].size()){
      |     ^~~
Main.cpp: In function 'int main()':
Main.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define rep(i,n) for(int i = 0; i < n; i++)
......
  134 |     rep(i, edges3.size()){
      |         ~~~~~~~~~~~~~~~~           
Main.cpp:134:5: note: in expansion of macro 'rep'
  134 |     rep(i, edges3.size()){
      |     ^~~
Main.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define rep(i,n) for(int i = 0; i < n; i++)
......
  136 |         rep(j, edges3[i].size()){
      |             ~~~~~~~~~~~~~~~~~~~    
Main.cpp:136:9: note: in expansion of macro 'rep'
  136 |         rep(j, edges3[i].size()){
      |         ^~~
Main.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define rep(i,n) for(int i = 0; i < n; i++)
......
  149 |     rep(i, eulerTour.size()){
      |         ~~~~~~~~~~~~~~~~~~~        
Main.cpp:149:5: note: in expansion of macro 'rep'
  149 |     rep(i, eulerTour.size()){
      |     ^~~
Main.cpp:105:9: warning: variable 'root' set but not used [-Wunused-but-set-variable]
  105 |     int root = -1;
      |         ^~~~
Main.cpp:117:9: warning: variable 'root2' set but not used [-Wunused-but-set-variable]
  117 |     int root2 = -1;
      |         ^~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24