제출 #95134

#제출 시각아이디문제언어결과실행 시간메모리
95134Retro3014Teleporters (IOI08_teleporters)C++17
85 / 100
769 ms66560 KiB
#include <iostream> #include <algorithm> #include <vector> #include <stdio.h> #define MAX_X 2000010 using namespace std; typedef long long ll; int N, M; struct S{ S(int x, int y) : x(x), y(y) {} int x, y; }; vector<S> v; int g[MAX_X+1]; vector<int> v2; int l[MAX_X+1], r[MAX_X+1]; bool vst[MAX_X+1]; vector<int> cycle; int ans; void dfs(int x, ll y){ if(vst[x]){ cycle.push_back(y); return; } vst[x] = true; if(x==v2.size()-1){ ans+=y; return; } dfs(r[x], y+1); } int main(){ scanf("%d%d", &N, &M); for(int i=0; i<N; i++){ int a, b; scanf("%d%d", &a, &b); v.push_back({a, b}); v2.push_back(a); v2.push_back(b); } v2.push_back(0); sort(v2.begin(), v2.end()); for(int i=0; i<v2.size(); i++){ g[v2[i]] = i; } for(int i=0; i<v.size(); i++){ S now = v[i]; r[g[now.x]-1] = g[now.y]; l[g[now.x]] = g[now.y]-1; r[g[now.y]-1] = g[now.x]; l[g[now.y]] = g[now.x]-1; } for(int i=0; i<v2.size(); i++){ if(vst[i]) continue; dfs(i, 0); } v2.clear(); /*printf("%d\n", ans); for(int i=0; i<cycle.size(); i++){ printf("%d\n", cycle[i]); }*/ sort(cycle.begin(), cycle.end()); while(M--){ if(cycle.empty()){ cycle.push_back(1); ans++; }else{ ans+=2+cycle.back(); cycle.pop_back(); } } printf("%d", ans); return 0; }

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

teleporters.cpp: In function 'void dfs(int, ll)':
teleporters.cpp:29:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(x==v2.size()-1){
     ~^~~~~~~~~~~~~
teleporters.cpp: In function 'int main()':
teleporters.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v2.size(); i++){
               ~^~~~~~~~~~
teleporters.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
teleporters.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v2.size(); i++){
               ~^~~~~~~~~~
teleporters.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
teleporters.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~
#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...
#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...
#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...
#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...