| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 1044365 |
2024-08-05T09:04:13 Z |
사상 최고의 알고리즘(#11062) |
Prize (CEOI22_prize) |
C++17 |
|
1120 ms |
424536 KB |
#include <bits/stdc++.h>
using namespace std;
int n,k,q,t;
int p0[1000005];
int p1[1000005];
vector<int> son0[1000005];
vector<int> son1[1000005];
vector<int> adj[1000005];
bool vis[1000005];
typedef pair<int,long long> P;
vector<P> vec;
vector<int> pt;
int dep0[1000005];
int dep1[1000005];
int par0[1000005][20];
int par1[1000005][20];
void dfs0(int v) {
for(int i=0;i<son0[v].size();i++) {
int nt=son0[v][i];
dep0[nt]=dep0[v]+1;
dfs0(nt);
}
}
void dfs1(int v) {
for(int i=0;i<son1[v].size();i++) {
int nt=son1[v][i];
dep1[nt]=dep1[v]+1;
dfs1(nt);
}
}
int lca0(int a,int b) {
if (dep0[a]<dep0[b]) {
swap(a,b);
}
int diff=dep0[a]-dep0[b];
for(int i=0;diff;i++) {
if (diff&1) {
a=par0[a][i];
}
diff/=2;
}
if (a!=b) {
for(int i=19;i>=0;i--) {
if (par0[a][i]!=par0[b][i]) {
a=par0[a][i];
b=par0[b][i];
}
}
a=par0[a][0];
}
return a;
}
int lca1(int a,int b) {
if (dep1[a]<dep1[b]) {
swap(a,b);
}
int diff=dep1[a]-dep1[b];
for(int i=0;diff;i++) {
if (diff&1) {
a=par1[a][i];
}
diff/=2;
}
if (a!=b) {
for(int i=19;i>=0;i--) {
if (par1[a][i]!=par1[b][i]) {
a=par1[a][i];
b=par1[b][i];
}
}
a=par1[a][0];
}
return a;
}
long long v00[1000005];
long long v01[1000005];
long long v10[1000005];
long long v11[1000005];
long long d0[1000005];
long long d1[1000005];
vector<P> v0[1000005];
vector<P> v1[1000005];
long long ret0[1000005];
long long ret1[1000005];
void f0(int v) {
for(int i=0;i<v0[v].size();i++) {
int nt=v0[v][i].first;
if (d0[nt]==-1) {
d0[nt]=d0[v]+v0[v][i].second;
f0(nt);
}
}
}
void f1(int v) {
for(int i=0;i<v1[v].size();i++) {
int nt=v1[v][i].first;
if (d1[nt]==-1) {
d1[nt]=d1[v]+v1[v][i].second;
f1(nt);
}
}
}
int main() {
scanf("%d %d %d %d",&n,&k,&q,&t);
int r0,r1;
memset(par0,-1,sizeof(par0));
memset(par1,-1,sizeof(par1));
for(int i=1;i<=n;i++) {
scanf("%d",&p0[i]);
par0[i][0]=p0[i];
if (p0[i]!=-1) {
son0[p0[i]].push_back(i);
}
else {
r0=i;
}
}
for(int i=1;i<=n;i++) {
scanf("%d",&p1[i]);
par1[i][0]=p1[i];
if (p1[i]!=-1) {
son1[p1[i]].push_back(i);
}
else {
r1=i;
}
}
dfs0(r0);
dfs1(r1);
for(int j=1;j<20;j++) {
for(int i=1;i<=n;i++) {
if (par0[i][j-1]!=-1) {
par0[i][j]=par0[par0[i][j-1]][j-1];
}
if (par1[i][j-1]!=-1) {
par1[i][j]=par1[par1[i][j-1]][j-1];
}
}
}
for(int i=1;i<=n;i++) {
if (son0[i].size()>=2) {
adj[son0[i][0]].push_back(son0[i][1]);
adj[son0[i][1]].push_back(son0[i][0]);
}
if (son1[i].size()>=2) {
adj[son1[i][0]].push_back(son1[i][1]);
adj[son1[i][1]].push_back(son1[i][0]);
}
}
int now;
for(int i=1;i<=n;i++) {
if (adj[i].size()<=1) {
now=i;
break;
}
}
vis[now]=true;
int id=1;
int pr=-1;
pt.push_back(now);
for(int cnt=1;cnt<k;cnt++) {
vis[now]=true;
int nt=-1;
for(int i=0;i<adj[now].size();i++) {
int nxt=adj[now][i];
if (nxt!=pr) {
nt=nxt;
break;
}
}
if (nt==-1) {
for(int i=id;i<=n;i++) {
if (!vis[i]) {
id=i+1;
nt=i;
break;
}
}
vec.push_back(P(now,nt));
pt.push_back(now);
pr=now;
now=nt;
continue;
}
if (vis[nt]) {
vec.push_back(P(now,nt));
for(int i=id;i<=n;i++) {
if (!vis[i]) {
id=i+1;
nt=i;
break;
}
}
pr=now;
now=nt;
pt.push_back(now);
continue;
}
vec.push_back(P(now,nt));
pr=now;
now=nt;
pt.push_back(now);
}
for(int i=0;i<k;i++) {
printf("%d ",pt[i]);
}
printf("\n");
for(int i=0;i<vec.size();i++) {
printf("%d %d\n",vec[i].first,vec[i].second);
}
printf("!\n");
fflush(stdout);
for(int i=0;i<k-1;i++) {
scanf("%lld %lld %lld %lld",&v00[i],&v01[i],&v10[i],&v11[i]);
}
for(int i=0;i<k-1;i++) {
int one=vec[i].first;
int two=vec[i].second;
//printf("%d %d\n",one,two);
int l0=lca0(one,two);
int l1=lca1(one,two);
//printf("%d %d %d %d\n",one,two,l0,l1);
v0[l0].push_back(P(one,v00[i]));
v0[l0].push_back(P(two,v01[i]));
v0[one].push_back(P(l0,-v00[i]));
v0[two].push_back(P(l1,-v01[i]));
v1[l1].push_back(P(one,v10[i]));
v1[l1].push_back(P(two,v11[i]));
v1[one].push_back(P(l1,-v10[i]));
v1[two].push_back(P(l1,-v11[i]));
}
memset(d0,-1,sizeof(d0));
memset(d1,-1,sizeof(d1));
d0[r0]=0;
d1[r1]=0;
f0(r0);
f1(r1);
for(int i=0;i<t;i++) {
int a,b;
scanf("%d %d",&a,&b);
//assert(d0[lca0(a,b)]!=-1);
//assert(d1[lca1(a,b)]!=-1);
ret0[i]=d0[a]+d0[b]-d0[lca0(a,b)]*2;
ret1[i]=d1[a]+d1[b]-d1[lca1(a,b)]*2;
}
for(int i=0;i<t;i++) {
printf("%lld %lld\n",ret0[i],ret1[i]);
}
fflush(stdout);
return 0;
}
Compilation message
Main.cpp: In function 'void dfs0(int)':
Main.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0;i<son0[v].size();i++) {
| ~^~~~~~~~~~~~~~~
Main.cpp: In function 'void dfs1(int)':
Main.cpp:28:18: 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=0;i<son1[v].size();i++) {
| ~^~~~~~~~~~~~~~~
Main.cpp: In function 'void f0(int)':
Main.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int i=0;i<v0[v].size();i++) {
| ~^~~~~~~~~~~~~
Main.cpp: In function 'void f1(int)':
Main.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i=0;i<v1[v].size();i++) {
| ~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:174:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for(int i=0;i<adj[now].size();i++) {
| ~^~~~~~~~~~~~~~~~
Main.cpp:218:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
218 | for(int i=0;i<vec.size();i++) {
| ~^~~~~~~~~~~
Main.cpp:219:21: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
219 | printf("%d %d\n",vec[i].first,vec[i].second);
| ~^
| |
| int
| %lld
Main.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | scanf("%d %d %d %d",&n,&k,&q,&t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | scanf("%d",&p0[i]);
| ~~~~~^~~~~~~~~~~~~
Main.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | scanf("%d",&p1[i]);
| ~~~~~^~~~~~~~~~~~~
Main.cpp:224:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
224 | scanf("%lld %lld %lld %lld",&v00[i],&v01[i],&v10[i],&v11[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:250:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
250 | scanf("%d %d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~
Main.cpp:246:7: warning: 'r0' may be used uninitialized in this function [-Wmaybe-uninitialized]
246 | f0(r0);
| ~~^~~~
Main.cpp:247:7: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
247 | f1(r1);
| ~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
481 ms |
348296 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
550 ms |
350284 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
496 ms |
366260 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1099 ms |
424536 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1120 ms |
406252 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
