제출 #782416

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
782416		vjudge1	통행료 (IOI18_highway)	C++17	51 / 100	206 ms	262144 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> adj[100100];
int dep[100100], par[100100];
vector<int> x;
void dfs(int n, int p = -1, int d = 0) {
    dep[n] = d;
    for(auto i: adj[n])
        if(i.first!=p)
            dfs(i.first, n, d+1), par[i.first] = i.second;
    x.push_back(n);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    for(int i = 0; i < N-1; i++)
        adj[U[i]].push_back({V[i], i}), adj[V[i]].push_back({U[i], i});
    dfs(0);
    int M = U.size();
    std::vector<int> w(M, 0);
    long long toll = ask(w);
    int dis = toll/A;
    while(x.size() > 1) {
        vector<int> a,b,c(N-1,0);
        for(int i = 0; i < x.size()/2; i++) {
            a.push_back(x[i]);
            c[par[x[i]]] = 1;
        }
        for(int i = x.size()/2; i < x.size(); i++) {
            b.push_back(x[i]);
        }
        if(ask(c)>toll)
            x = a;
        else 
            x = b;
    }
    int temp = x[0];
    dfs(x[0]);
    x.clear();
    for(int i = 0; i < N; i++)
        if(dep[i]==dis)
            x.push_back(i);
    while(x.size() > 1) {
        vector<int> a,b,c(N-1,0);
        for(int i = 0; i < x.size()/2; i++) {
            a.push_back(x[i]);
            c[par[x[i]]] = 1;
        }
        for(int i = x.size()/2; i < x.size(); i++) {
            b.push_back(x[i]);
        }
        if(ask(c)>toll)
            x = a;
        else 
            x = b;
    }
    answer(temp, x[0]);
}

컴파일 시 표준 에러 (stderr) 메시지

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:24:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(int i = 0; i < x.size()/2; i++) {
      |                        ~~^~~~~~~~~~~~
highway.cpp:28:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int i = x.size()/2; i < x.size(); i++) {
      |                                 ~~^~~~~~~~~~
highway.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int i = 0; i < x.size()/2; i++) {
      |                        ~~^~~~~~~~~~~~
highway.cpp:48:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int i = x.size()/2; i < x.size(); i++) {
      |                                 ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31