답안 #820294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
820294	2023-08-11T03:54:52 Z	damwuan	자매 도시 (APIO20_swap)	C++17	100 / 100	278 ms	65228 KB

swap

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=4e5+69;
const ll offset=1e9;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=1e9+7;
int n,par[maxn],m,deg[maxn],val[maxn],up[maxn][20],in[maxn],out[maxn],Time,ans[maxn];
bool ok[maxn];
vector<int> adj[maxn];
pair<int,pii> Edge[maxn];
map<pii,int> L;
int Find(int u)
{
    return (par[u]<0?u:par[u]=Find(par[u]));
}
void AddEdge(int u,int v,int w)
{
    val[n]=w;
    deg[u]++;
    deg[v]++;
    if (deg[u]>2 || deg[v]>2) ok[n]=1;
    u=Find(u);
    v=Find(v);
    par[n]+=par[u];
    par[u]=n;
    adj[n].pb(u);
    if (u!=v)
    {
        adj[n].pb(v);
        par[n]+=par[v];
        par[v]=n;
    }
    ok[n]=ok[n]|ok[u]|ok[v];
    //cerr<<n<<' '<<ok[n]<<' '<<val[n]<< " kk\n";
    n++;
}
void dfs(int u,int pre)
{
    in[u]=++Time;
    up[u][0]=pre;
    for1(i,1,19)
    {
        up[u][i]=up[up[u][i-1]][i-1];
    }
    if (ok[u]||adj[u].size()==1) ans[u]=val[u];
    else if (u!=pre) ans[u]=ans[pre];
    else ans[u]=-1;
    //cerr <<"acac "<<u<<' '<<ans[u]<<'\n';
    for(int v: adj[u])
    {
        dfs(v,u);
    }
    out[u]=Time;
}
bool is_ancestor(int u,int v)
{
    return (in[u]<=in[v] && out[v] <= out[u]);
}
int lca(int u,int v)
{
    if (is_ancestor(u,v)) return u;
    if (is_ancestor(v,u)) return v;
    for2(i,19,0)
    {
        if (!is_ancestor(up[u][i],v)) u=up[u][i];
    }
    return up[u][0];
}
void init(int N,int M,vector<int> U,vector<int> V, vector<int> W)
{
    n=N;
    m=M;
    for1(i,0,n+m) par[i]=-1;
    for1(i,0,m-1)
    {
        Edge[i+1]={W[i],{U[i],V[i]}};
        //L[{U[i],V[i]}]=W[i];
    }
    sort(Edge+1,Edge+1+m);
    for1(i,1,m)
    {
        AddEdge(Edge[i].se.fi,Edge[i].se.se,Edge[i].fi);
    }
    dfs(n-1,n-1);
}
int getMinimumFuelCapacity(int X, int Y) {
  return ans[lca(X,Y)];
}

//
//int main() {
//  int N, M;
//  assert(2 == scanf("%d %d", &N, &M));
//
//  std::vector<int> U(M), V(M), W(M);
//  for (int i = 0; i < M; ++i) {
//    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
//  }
//
//  int Q;
//  assert(1 == scanf("%d", &Q));
//
//  std::vector<int> X(Q), Y(Q);
//  for (int i = 0; i < Q; ++i) {
//    assert(2 == scanf("%d %d", &X[i], &Y[i]));
//  }
//
//  init(N, M, U, V, W);
//
//  std::vector<int> minimum_fuel_capacities(Q);
//  for (int i = 0; i < Q; ++i) {
//    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
//  }
//
//  for (int i = 0; i < Q; ++i) {
//    printf("%d\n", minimum_fuel_capacities[i]);
//  }
//
//  return 0;
//}

Subtask #1

6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	4 ms	9648 KB	Output is correct
3	Correct	4 ms	9684 KB	Output is correct
4	Correct	4 ms	9812 KB	Output is correct
5	Correct	5 ms	9940 KB	Output is correct
6	Correct	5 ms	9952 KB	Output is correct
7	Correct	4 ms	9940 KB	Output is correct
8	Correct	5 ms	10024 KB	Output is correct
9	Correct	80 ms	30412 KB	Output is correct
10	Correct	119 ms	35016 KB	Output is correct
11	Correct	94 ms	34600 KB	Output is correct
12	Correct	103 ms	36028 KB	Output is correct
13	Correct	81 ms	38280 KB	Output is correct
14	Correct	80 ms	30412 KB	Output is correct
15	Correct	173 ms	37032 KB	Output is correct
16	Correct	158 ms	36320 KB	Output is correct
17	Correct	170 ms	37760 KB	Output is correct
18	Correct	182 ms	40120 KB	Output is correct
19	Correct	68 ms	17300 KB	Output is correct
20	Correct	165 ms	38204 KB	Output is correct
21	Correct	162 ms	37444 KB	Output is correct
22	Correct	180 ms	39256 KB	Output is correct
23	Correct	188 ms	41508 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	4 ms	9648 KB	Output is correct
3	Correct	167 ms	42016 KB	Output is correct
4	Correct	191 ms	43532 KB	Output is correct
5	Correct	174 ms	42756 KB	Output is correct
6	Correct	186 ms	43364 KB	Output is correct
7	Correct	186 ms	43092 KB	Output is correct
8	Correct	189 ms	41808 KB	Output is correct
9	Correct	173 ms	42812 KB	Output is correct
10	Correct	172 ms	41552 KB	Output is correct

Subtask #3

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	4 ms	9648 KB	Output is correct
3	Correct	4 ms	9684 KB	Output is correct
4	Correct	4 ms	9812 KB	Output is correct
5	Correct	5 ms	9940 KB	Output is correct
6	Correct	5 ms	9952 KB	Output is correct
7	Correct	4 ms	9940 KB	Output is correct
8	Correct	5 ms	10024 KB	Output is correct
9	Correct	6 ms	9684 KB	Output is correct
10	Correct	5 ms	9940 KB	Output is correct
11	Correct	5 ms	9940 KB	Output is correct
12	Correct	5 ms	9940 KB	Output is correct
13	Correct	5 ms	9940 KB	Output is correct
14	Correct	5 ms	9940 KB	Output is correct
15	Correct	6 ms	9940 KB	Output is correct
16	Correct	5 ms	9940 KB	Output is correct
17	Correct	5 ms	9940 KB	Output is correct
18	Correct	6 ms	9940 KB	Output is correct
19	Correct	5 ms	9976 KB	Output is correct
20	Correct	5 ms	9928 KB	Output is correct
21	Correct	5 ms	9940 KB	Output is correct
22	Correct	5 ms	10068 KB	Output is correct
23	Correct	5 ms	9940 KB	Output is correct
24	Correct	5 ms	10068 KB	Output is correct
25	Correct	6 ms	10068 KB	Output is correct
26	Correct	5 ms	10196 KB	Output is correct
27	Correct	5 ms	9940 KB	Output is correct
28	Correct	5 ms	10196 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	9684 KB	Output is correct
2	Correct	4 ms	9684 KB	Output is correct
3	Correct	4 ms	9648 KB	Output is correct
4	Correct	4 ms	9684 KB	Output is correct
5	Correct	4 ms	9812 KB	Output is correct
6	Correct	5 ms	9940 KB	Output is correct
7	Correct	5 ms	9952 KB	Output is correct
8	Correct	4 ms	9940 KB	Output is correct
9	Correct	5 ms	10024 KB	Output is correct
10	Correct	80 ms	30412 KB	Output is correct
11	Correct	119 ms	35016 KB	Output is correct
12	Correct	94 ms	34600 KB	Output is correct
13	Correct	103 ms	36028 KB	Output is correct
14	Correct	81 ms	38280 KB	Output is correct
15	Correct	5 ms	9940 KB	Output is correct
16	Correct	5 ms	9940 KB	Output is correct
17	Correct	5 ms	9940 KB	Output is correct
18	Correct	5 ms	9940 KB	Output is correct
19	Correct	5 ms	9940 KB	Output is correct
20	Correct	6 ms	9940 KB	Output is correct
21	Correct	5 ms	9940 KB	Output is correct
22	Correct	5 ms	9940 KB	Output is correct
23	Correct	6 ms	9940 KB	Output is correct
24	Correct	5 ms	9976 KB	Output is correct
25	Correct	5 ms	9928 KB	Output is correct
26	Correct	5 ms	9940 KB	Output is correct
27	Correct	5 ms	10068 KB	Output is correct
28	Correct	5 ms	9940 KB	Output is correct
29	Correct	5 ms	10068 KB	Output is correct
30	Correct	6 ms	10068 KB	Output is correct
31	Correct	5 ms	10196 KB	Output is correct
32	Correct	5 ms	9940 KB	Output is correct
33	Correct	5 ms	10196 KB	Output is correct
34	Correct	13 ms	13268 KB	Output is correct
35	Correct	108 ms	36024 KB	Output is correct
36	Correct	105 ms	36016 KB	Output is correct
37	Correct	97 ms	36028 KB	Output is correct
38	Correct	97 ms	35664 KB	Output is correct
39	Correct	96 ms	35560 KB	Output is correct
40	Correct	90 ms	33356 KB	Output is correct
41	Correct	104 ms	36060 KB	Output is correct
42	Correct	99 ms	35976 KB	Output is correct
43	Correct	82 ms	39036 KB	Output is correct
44	Correct	111 ms	36224 KB	Output is correct
45	Correct	116 ms	46004 KB	Output is correct
46	Correct	98 ms	37884 KB	Output is correct
47	Correct	100 ms	37928 KB	Output is correct
48	Correct	105 ms	41432 KB	Output is correct
49	Correct	95 ms	46028 KB	Output is correct
50	Correct	69 ms	38092 KB	Output is correct
51	Correct	106 ms	43808 KB	Output is correct
52	Correct	139 ms	52428 KB	Output is correct
53	Correct	161 ms	55472 KB	Output is correct
54	Correct	164 ms	61180 KB	Output is correct
55	Correct	81 ms	40660 KB	Output is correct
56	Correct	164 ms	56256 KB	Output is correct

Subtask #5

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	9684 KB	Output is correct
2	Correct	4 ms	9648 KB	Output is correct
3	Correct	4 ms	9684 KB	Output is correct
4	Correct	4 ms	9812 KB	Output is correct
5	Correct	5 ms	9940 KB	Output is correct
6	Correct	5 ms	9952 KB	Output is correct
7	Correct	4 ms	9940 KB	Output is correct
8	Correct	5 ms	10024 KB	Output is correct
9	Correct	80 ms	30412 KB	Output is correct
10	Correct	119 ms	35016 KB	Output is correct
11	Correct	94 ms	34600 KB	Output is correct
12	Correct	103 ms	36028 KB	Output is correct
13	Correct	81 ms	38280 KB	Output is correct
14	Correct	80 ms	30412 KB	Output is correct
15	Correct	173 ms	37032 KB	Output is correct
16	Correct	158 ms	36320 KB	Output is correct
17	Correct	170 ms	37760 KB	Output is correct
18	Correct	182 ms	40120 KB	Output is correct
19	Correct	167 ms	42016 KB	Output is correct
20	Correct	191 ms	43532 KB	Output is correct
21	Correct	174 ms	42756 KB	Output is correct
22	Correct	186 ms	43364 KB	Output is correct
23	Correct	186 ms	43092 KB	Output is correct
24	Correct	189 ms	41808 KB	Output is correct
25	Correct	173 ms	42812 KB	Output is correct
26	Correct	172 ms	41552 KB	Output is correct
27	Correct	5 ms	9940 KB	Output is correct
28	Correct	5 ms	9940 KB	Output is correct
29	Correct	5 ms	9940 KB	Output is correct
30	Correct	5 ms	9940 KB	Output is correct
31	Correct	5 ms	9940 KB	Output is correct
32	Correct	6 ms	9940 KB	Output is correct
33	Correct	5 ms	9940 KB	Output is correct
34	Correct	5 ms	9940 KB	Output is correct
35	Correct	6 ms	9940 KB	Output is correct
36	Correct	13 ms	13268 KB	Output is correct
37	Correct	108 ms	36024 KB	Output is correct
38	Correct	105 ms	36016 KB	Output is correct
39	Correct	97 ms	36028 KB	Output is correct
40	Correct	97 ms	35664 KB	Output is correct
41	Correct	96 ms	35560 KB	Output is correct
42	Correct	90 ms	33356 KB	Output is correct
43	Correct	104 ms	36060 KB	Output is correct
44	Correct	99 ms	35976 KB	Output is correct
45	Correct	82 ms	39036 KB	Output is correct
46	Correct	111 ms	36224 KB	Output is correct
47	Correct	19 ms	13268 KB	Output is correct
48	Correct	175 ms	38580 KB	Output is correct
49	Correct	167 ms	38628 KB	Output is correct
50	Correct	170 ms	38576 KB	Output is correct
51	Correct	170 ms	38396 KB	Output is correct
52	Correct	170 ms	36932 KB	Output is correct
53	Correct	141 ms	30736 KB	Output is correct
54	Correct	171 ms	39200 KB	Output is correct
55	Correct	202 ms	38552 KB	Output is correct
56	Correct	186 ms	41012 KB	Output is correct
57	Correct	185 ms	39272 KB	Output is correct

Subtask #6

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	9684 KB	Output is correct
2	Correct	4 ms	9684 KB	Output is correct
3	Correct	4 ms	9648 KB	Output is correct
4	Correct	4 ms	9684 KB	Output is correct
5	Correct	4 ms	9812 KB	Output is correct
6	Correct	5 ms	9940 KB	Output is correct
7	Correct	5 ms	9952 KB	Output is correct
8	Correct	4 ms	9940 KB	Output is correct
9	Correct	5 ms	10024 KB	Output is correct
10	Correct	80 ms	30412 KB	Output is correct
11	Correct	119 ms	35016 KB	Output is correct
12	Correct	94 ms	34600 KB	Output is correct
13	Correct	103 ms	36028 KB	Output is correct
14	Correct	81 ms	38280 KB	Output is correct
15	Correct	80 ms	30412 KB	Output is correct
16	Correct	173 ms	37032 KB	Output is correct
17	Correct	158 ms	36320 KB	Output is correct
18	Correct	170 ms	37760 KB	Output is correct
19	Correct	182 ms	40120 KB	Output is correct
20	Correct	167 ms	42016 KB	Output is correct
21	Correct	191 ms	43532 KB	Output is correct
22	Correct	174 ms	42756 KB	Output is correct
23	Correct	186 ms	43364 KB	Output is correct
24	Correct	186 ms	43092 KB	Output is correct
25	Correct	189 ms	41808 KB	Output is correct
26	Correct	173 ms	42812 KB	Output is correct
27	Correct	172 ms	41552 KB	Output is correct
28	Correct	5 ms	9940 KB	Output is correct
29	Correct	5 ms	9940 KB	Output is correct
30	Correct	5 ms	9940 KB	Output is correct
31	Correct	5 ms	9940 KB	Output is correct
32	Correct	5 ms	9940 KB	Output is correct
33	Correct	6 ms	9940 KB	Output is correct
34	Correct	5 ms	9940 KB	Output is correct
35	Correct	5 ms	9940 KB	Output is correct
36	Correct	6 ms	9940 KB	Output is correct
37	Correct	13 ms	13268 KB	Output is correct
38	Correct	108 ms	36024 KB	Output is correct
39	Correct	105 ms	36016 KB	Output is correct
40	Correct	97 ms	36028 KB	Output is correct
41	Correct	97 ms	35664 KB	Output is correct
42	Correct	96 ms	35560 KB	Output is correct
43	Correct	90 ms	33356 KB	Output is correct
44	Correct	104 ms	36060 KB	Output is correct
45	Correct	99 ms	35976 KB	Output is correct
46	Correct	82 ms	39036 KB	Output is correct
47	Correct	111 ms	36224 KB	Output is correct
48	Correct	19 ms	13268 KB	Output is correct
49	Correct	175 ms	38580 KB	Output is correct
50	Correct	167 ms	38628 KB	Output is correct
51	Correct	170 ms	38576 KB	Output is correct
52	Correct	170 ms	38396 KB	Output is correct
53	Correct	170 ms	36932 KB	Output is correct
54	Correct	141 ms	30736 KB	Output is correct
55	Correct	171 ms	39200 KB	Output is correct
56	Correct	202 ms	38552 KB	Output is correct
57	Correct	186 ms	41012 KB	Output is correct
58	Correct	185 ms	39272 KB	Output is correct
59	Correct	68 ms	17300 KB	Output is correct
60	Correct	165 ms	38204 KB	Output is correct
61	Correct	162 ms	37444 KB	Output is correct
62	Correct	180 ms	39256 KB	Output is correct
63	Correct	188 ms	41508 KB	Output is correct
64	Correct	5 ms	9976 KB	Output is correct
65	Correct	5 ms	9928 KB	Output is correct
66	Correct	5 ms	9940 KB	Output is correct
67	Correct	5 ms	10068 KB	Output is correct
68	Correct	5 ms	9940 KB	Output is correct
69	Correct	5 ms	10068 KB	Output is correct
70	Correct	6 ms	10068 KB	Output is correct
71	Correct	5 ms	10196 KB	Output is correct
72	Correct	5 ms	9940 KB	Output is correct
73	Correct	5 ms	10196 KB	Output is correct
74	Correct	116 ms	46004 KB	Output is correct
75	Correct	98 ms	37884 KB	Output is correct
76	Correct	100 ms	37928 KB	Output is correct
77	Correct	105 ms	41432 KB	Output is correct
78	Correct	95 ms	46028 KB	Output is correct
79	Correct	69 ms	38092 KB	Output is correct
80	Correct	106 ms	43808 KB	Output is correct
81	Correct	139 ms	52428 KB	Output is correct
82	Correct	161 ms	55472 KB	Output is correct
83	Correct	164 ms	61180 KB	Output is correct
84	Correct	81 ms	40660 KB	Output is correct
85	Correct	164 ms	56256 KB	Output is correct
86	Correct	59 ms	24448 KB	Output is correct
87	Correct	170 ms	42672 KB	Output is correct
88	Correct	174 ms	42652 KB	Output is correct
89	Correct	195 ms	44712 KB	Output is correct
90	Correct	167 ms	52112 KB	Output is correct
91	Correct	195 ms	49364 KB	Output is correct
92	Correct	220 ms	47612 KB	Output is correct
93	Correct	214 ms	56624 KB	Output is correct
94	Correct	277 ms	59996 KB	Output is correct
95	Correct	234 ms	65228 KB	Output is correct
96	Correct	181 ms	45404 KB	Output is correct
97	Correct	278 ms	52784 KB	Output is correct