Submission #480937

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
480937	2021-10-18 20:52:15	peti1234	Race (IOI11_race)	C++17	100 / 100	522 ms	101504 KiB

race

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int c=200005;
int szint[c], ki[c];
long long dist[c], cel, ans=c;
map<long long, long long> m[c];
vector<pair<int, int> > sz[c];
bool v[c];
void unio(int a, int b) {
    int aa=ki[a], bb=ki[b], sa=m[aa].size(), sb=m[bb].size();
    long long ert=cel+2*dist[a];
    if (sa>=sb) {
        for (auto p:m[bb]) {
            long long fi=p.first, se=p.second, inv=ert-fi;
            if (m[aa].find(inv)!=m[aa].end()) {
                ans=min(ans, se+m[aa][inv]-2*szint[a]);
            }
        }
        for (auto p:m[bb]) {
            long long fi=p.first, se=p.second;
            if (m[aa].find(fi)!=m[aa].end()) {
                m[aa][fi]=min(m[aa][fi], se);
            } else {
                m[aa][fi]=se;
            }
        }
    } else {
        ki[a]=bb;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57