Submission #315264

#	Time	Username	Problem	Language	Result	Execution time	Memory
315264		mosiashvililuka	City (JOI17_city)	C++14	22 / 100	637 ms	78320 KiB

Encoder

#include<bits/stdc++.h>
#include "Encoder.h"
using namespace std;
const long long N=250009;
long long a,b,c,d,e,i,j,lf[250009],rg[250009],f[250009],tim;
vector <long long> v[250009];
void dfs(long long q, long long w){
	tim++;
	lf[q]=rg[q]=tim;
	for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it)==w) continue;
		dfs((*it),q);
		if(rg[q]<rg[(*it)]) rg[q]=rg[(*it)];
	}
}
void Encode(int n, int A[], int B[]){
	a=n;
	for(i=0; i<a-1; i++){
		v[A[i]+1].push_back(B[i]+1);
		v[B[i]+1].push_back(A[i]+1);
	}
	dfs(1,0);
	for(i=1; i<=a; i++) Code(i-1,lf[i]*N+rg[i]);
}

Device

#include<bits/stdc++.h>
#include "Device.h"
using namespace std;
const long long n=250009;
long long l[4],r[4];
void InitDevice() {
    
}
bool anc(long long q, long long w){
	if(l[q]<=l[w]&&r[q]>=r[w]) return 1; else return 0;
}
int Answer(long long S, long long T) {
	swap(S,T);
    l[1]=S/n;r[1]=S%n;
    l[2]=T/n;r[2]=T%n;
    if(anc(1,2)) return 0;
    if(anc(2,1)) return 1;
    return 2;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 92