이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<ll, ii> ip;
#define MAXN 800200
#define INF 1001001001001001001LL
//ll dp[1 << MAXN][LOG], reza = INF;
unordered_map<int, int> mp;
vector<int> g[MAXN], in[MAXN];
set<int> s2;
vector<int> s, z;
unordered_map<int, int> ss;
ll reza = 0;
int zip(int x)
{
if (mp.count(x)) return mp[x];
return mp[x] = mp.size();
}
int bio[MAXN];
int rt[MAXN], sz[MAXN];
set<int> co;
void dfs(int cv, int kor)
{
if (bio[cv]) return;
bio[cv] = 1;
rt[cv] = kor;
co.insert(kor);
for (int i: g[cv])
dfs(i, kor);
for (int i: in[cv])
dfs(i, kor);
}
int fn(int cv)
{
if (cv == rt[cv]) return cv;
return rt[cv] = fn(rt[cv]);
}
void merg(int x, int y)
{
x = fn(x);
y = fn(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
rt[x] = y;
co.erase(x);
if (sz[x] == sz[y]) sz[y]++;
}
set<ip> es;
long long plan_roller_coaster(std::vector<int> _s, std::vector<int> t) {
int n = (int) _s.size();
_s.pb(1001001001); t.pb(1); n++;
for (int i = 0; i < n; i++) {
int _sz = zip(_s[i]), tz = zip(t[i]);
g[_sz].pb(tz);
in[tz].pb(_sz);
s2.insert(_s[i]);
s2.insert(t[i]);
ss[_s[i]]++;
ss[t[i]]--;
}
for (int i: s2) { s.pb(i); z.pb(zip(i)); }
int suma = 0;
for (int j = 0; j < s.size() - 1; j++) {
int i = s[j];
int ni = s[j + 1];
suma += ss[i];
if (suma > 0) {
reza += ll(suma) * ll(ni - i);
i = z[j];
ni = z[j + 1];
g[ni].pb(i);
in[i].pb(ni);
//cout<<i<<' '<<ni<<'='<<suma<<endl;
}
if (suma < 0) {
i = z[j];
ni = z[j + 1];
g[ni].pb(i);
in[i].pb(ni);
}
}
for (int j = 0; j < s.size(); j++) {
int i = s[j];
dfs(z[j], z[j]);
//cout << i<<' '<<rt[zip(i)]<<endl;
}return 0;
for (int j = 0; j < s.size() - 1; j++) {
int i = s[j];
int ni = s[j + 1];
es.insert({ll(ni) - i, {z[j], z[j + 1]}});//cout<<ll(ni)-i<<' '<<i<<'.'<<ni<<' '<<zip(i)<<'.'<<zip(ni)<<endl;
}
while (co.size() > 1) {
ip cu = *es.begin();//cout<<cu.X<<' '<<cu.Y.X<<'.'<<cu.Y.Y<<endl;
es.erase(cu);//cout<<cu.X<<' '<<cu.Y.X<<'.'<<cu.Y.Y<<' '<<co.size()<<','<<reza<<endl;
int pre = co.size();
merg(cu.Y.X, cu.Y.Y);
int nov = co.size();
if (nov < pre) reza += cu.X;
}
return reza;
}
컴파일 시 표준 에러 (stderr) 메시지
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:89:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for (int j = 0; j < s.size() - 1; j++) {
| ~~^~~~~~~~~~~~~~
railroad.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for (int j = 0; j < s.size(); j++) {
| ~~^~~~~~~~~~
railroad.cpp:110:8: warning: unused variable 'i' [-Wunused-variable]
110 | int i = s[j];
| ^
railroad.cpp:115:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for (int j = 0; j < s.size() - 1; j++) {
| ~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |