답안 #979565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
979565	2024-05-11T07:50:35 Z	vjudge1	자매 도시 (APIO20_swap)	C++17	6 / 100	140 ms	15048 KB

swap

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N =3e5 + 9 , mod = 1e9 + 7;
ll  p[N][3] , sz[N]  ;

vector<pair<ll,ll>>vv;
int get(int x , vector<pair<ll,ll>>&vv ){
    if(vv.size())
        vv.pb({x , p[x][1] });
    return (p[x][0] == x ? x : get(p[x][0] , vv));
}
void join(int x , int y , ll k){
    x = get(x , vv) , y = get(y , vv);
    if(x != y){
        if(sz[x] < sz[y])
            swap(x , y);
        p[y][0] = x;
        p[y][1] = k;
        p[x][2] = min(p[y][2] , p[x][2]);
        sz[x] += sz[y];
    }else {
        p[y][2] = min(p[y][2] , k);
    }
}
void init(int n , int m , vector<int>v , vector<int>u , vector<int>c)
{
    vector<pair<ll,pair<ll,ll>>>vc;
    for(int i = 0; i <= n; i++)
        p[i][0] =  i , p[i][1] = 0, p[i][2] = 1e18 , sz[i] = 1;
    for(int i = 0; i < m; i++)
        vc.pb({c[i] , {v[i] + 1, u[i] + 1}});
    sort(all(vc));
    for(auto to : vc){
        join(to.se.fi , to.se.se , to.fi);
    }
}

int getMinimumFuelCapacity(int l, int r) {
        l++ , r++;

        vector<pair<ll,ll>>v1 = {{0 , 0}}, v2= {{-1 , 0}};
        get(l , v1);
        get(r , v2);
        ll x = v1.size() - 1,  y =  v2.size() - 1;
        ll mx = 0 , mn = 1e18;
        while(1){
            mn = min({mn , max(v1[x].se , p[v1[x].fi][2] )});
            if(v1[x].fi != v2[y].fi){
                mx = max({mx , v1[x].se , v2[y].se });
                break;
            }
            x-- , y--;
        }
        mx = max(mx , mn);
        /*while(1){
            if(v1[x].fi != v2[y].fi){
                mx = max({mx , v1[x].se , v2[y].se });
                break;
            }
            x-- , y--;
        }
        */
        if(mx == 1e18)
            mx = -1;
        return mx;
	return mx;
}
/*
int main(){
    init(5, 6, {0, 0, 1, 1, 1, 2}, {1, 2, 2, 3, 4, 3}, {4, 4, 1, 2, 10, 3});
    cout<<getMinimumFuelCapacity(1,2)<<"\n";
    cout<<getMinimumFuelCapacity(2,4)<<"\n";
    cout<<getMinimumFuelCapacity(0,1)<<"\n";
}*/

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2500 KB	Output is correct
5	Correct	1 ms	2492 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	36 ms	9708 KB	Output is correct
10	Correct	44 ms	12024 KB	Output is correct
11	Correct	37 ms	11972 KB	Output is correct
12	Correct	36 ms	12224 KB	Output is correct
13	Correct	36 ms	12240 KB	Output is correct
14	Correct	37 ms	11212 KB	Output is correct
15	Correct	131 ms	14412 KB	Output is correct
16	Correct	140 ms	14792 KB	Output is correct
17	Correct	121 ms	13760 KB	Output is correct
18	Correct	101 ms	15044 KB	Output is correct
19	Correct	94 ms	6528 KB	Output is correct
20	Correct	125 ms	14280 KB	Output is correct
21	Correct	121 ms	14788 KB	Output is correct
22	Correct	124 ms	14296 KB	Output is correct
23	Correct	112 ms	15048 KB	Output is correct

Subtask #2
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Incorrect	95 ms	14788 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2500 KB	Output is correct
5	Correct	1 ms	2492 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2392 KB	Output is correct
10	Incorrect	1 ms	2396 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2500 KB	Output is correct
6	Correct	1 ms	2492 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	36 ms	9708 KB	Output is correct
11	Correct	44 ms	12024 KB	Output is correct
12	Correct	37 ms	11972 KB	Output is correct
13	Correct	36 ms	12224 KB	Output is correct
14	Correct	36 ms	12240 KB	Output is correct
15	Incorrect	1 ms	2396 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	2500 KB	Output is correct
5	Correct	1 ms	2492 KB	Output is correct
6	Correct	1 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	36 ms	9708 KB	Output is correct
10	Correct	44 ms	12024 KB	Output is correct
11	Correct	37 ms	11972 KB	Output is correct
12	Correct	36 ms	12224 KB	Output is correct
13	Correct	36 ms	12240 KB	Output is correct
14	Correct	37 ms	11212 KB	Output is correct
15	Correct	131 ms	14412 KB	Output is correct
16	Correct	140 ms	14792 KB	Output is correct
17	Correct	121 ms	13760 KB	Output is correct
18	Correct	101 ms	15044 KB	Output is correct
19	Incorrect	95 ms	14788 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2500 KB	Output is correct
6	Correct	1 ms	2492 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	36 ms	9708 KB	Output is correct
11	Correct	44 ms	12024 KB	Output is correct
12	Correct	37 ms	11972 KB	Output is correct
13	Correct	36 ms	12224 KB	Output is correct
14	Correct	36 ms	12240 KB	Output is correct
15	Correct	37 ms	11212 KB	Output is correct
16	Correct	131 ms	14412 KB	Output is correct
17	Correct	140 ms	14792 KB	Output is correct
18	Correct	121 ms	13760 KB	Output is correct
19	Correct	101 ms	15044 KB	Output is correct
20	Incorrect	95 ms	14788 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

답안 #979565

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 0 / 7.0

Subtask #3 0 / 17.0

Subtask #4 0 / 20.0

Subtask #5 0 / 23.0

Subtask #6 0 / 27.0

Subtask #1
6.0 / 6.0

Subtask #2
0 / 7.0

Subtask #3
0 / 17.0

Subtask #4
0 / 20.0

Subtask #5
0 / 23.0

Subtask #6
0 / 27.0