제출 #828359

#제출 시각아이디문제언어결과실행 시간메모리
828359minhcool기지국 (IOI20_stations)C++17
36.31 / 100
670 ms24356 KiB
#include "stations.h" #include<bits/stdc++.h> using namespace std; #include <vector> #define pb push_back #define fi first #define se second #define pb push_back typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 5e5 + 5, oo = 1e18 + 7; int n; vector<int> Adj[N]; int l[N], r[N]; vector<int> vis; void dfs(int u, int p){ vis.pb(u); l[u] = vis.size(); for(auto v : Adj[u]){ if(v == p) continue; dfs(v, u); } r[u] = vis.size(); } //vector<int> vis; int tol[1005][1005]; ii tol2[600005]; /* void prep(){ int cnt = 0; for(int i = 1; i <= 1000; i++){ for(int j = i; j <= 1000; j++){ tol[i][j] = cnt; tol2[cnt] = {i, j}; cnt++; } } }*/ vector<int> label(int n_, int k, vector<int> u, vector<int> v) { n = n_; vis.clear(); for(int i = 0; i < n; i++) Adj[i].clear(); for(int i = 0; i < (n - 1); i++){ Adj[u[i]].pb(v[i]); Adj[v[i]].pb(u[i]); } dfs(0, 0); vector<int> labels(n); for(int i = 0; i < n; i++){ //cout << l[i] << " " << r[i] << " " << tol[l[i]][r[i]] << "\n"; //labels[i] = tol[l[i]][r[i]]; labels[i] = l[i] * 1001 + r[i]; } return labels; /* std::vector<int> labels(n); for (int i = 0; i < n; i++) { labels[i] = i; } return labels;*/ } bool anc(int lab1, int lab2){ ii temp1 = {lab1 / 1001, lab1 % 1001}, temp2 = {lab2 / 1001, lab2 % 1001}; return (temp1.fi <= temp2.fi && temp1.se >= temp2.se); } int find_next_station(int s, int t, vector<int> c) { //cout << c.size() << "\n"; //return 0; pair<int, int> mini = {oo, oo}, maxi = {-1, -1}; for(int i = 0; i < c.size(); i++){ ii tempo = {c[i] / 1001, c[i] % 1001}; maxi = max(maxi, {tempo.se - tempo.fi + 1, c[i]}); if(anc(c[i], t)){ mini = min(mini, {tempo.se - tempo.fi + 1, c[i]}); } } if(mini.se != oo) return mini.se; else return maxi.se; /* if(anc(c[1], t)) return c[1]; else if(anc(c[2], t)) return c[2]; else return c[0];*/ //return c[0]; }

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

stations.cpp:15:34: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const int N = 5e5 + 5, oo = 1e18 + 7;
      |                             ~~~~~^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:83:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(int i = 0; i < c.size(); i++){
      |                 ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...