Submission #943508

#	Time	Username	Problem	Language	Result	Execution time	Memory
943508		guagua0407	Capital City (JOI20_capital_city)	C++17	100 / 100	102 ms	35704 KiB

capital_city

#pragma GCC optimize(3,"Ofast","inline")
#pragma G++ optimize(3,"Ofast","inline")

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>

#define R                  register int
#define re(i,a,b)          for(R i=a; i<=b; i++)
#define ms(i,a)            memset(a,i,sizeof(a))
#define MAX(a,b)           (((a)>(b)) ? (a):(b))
#define MIN(a,b)           (((a)<(b)) ? (a):(b))

using namespace std;

typedef long long LL;

namespace IO {
	#include <cctype>

	template <typename T>
	inline void read(T &x){
		x=0;
		char c=0;
		T w=0;
		while (!isdigit(c)) w|=c=='-',c=getchar();
		while (isdigit(c)) x=x*10+(c^48),c=getchar();
		if(w) x=-x;
	}

	template <typename T>
	inline void write(T x) {
	    if(x<0) putchar('-'),x=-x;
	    if(x<10) putchar(x+'0');
	        else write(x/10),putchar(x%10+'0');
	}

	template <typename T>
	inline void writeln(T x) {
	    write(x);
	    putchar('\n');
	}
}

using IO::read;
using IO::write;
using IO::writeln;

const int N=2e5+5;

int n,k,clk,scc,ans;
int dfn[N],c[N],mn[N],rr[N],idfn[N],f[N],low[N],st[N],tp,sz[N],bel[N];
bool ins[N],ban[N];
vector<int> e[N],v[N];

inline void cmin(int &x,int y) {
	y < x ? x= y : 0;
}

void dfs(int x) {
    idfn[dfn[x]=++clk]=x;
    for(int i=0,y; i<e[x].size(); i++)
        if(!dfn[y=e[x][i]]) f[y]=x,dfs(y);
    rr[x]=clk;
}

void tarjan(int x) {
    dfn[x]=low[x]=++clk;
	st[++tp]=x;
	ins[x]=1;
    for(int i=0,y; i<v[x].size(); i++)
        if(!dfn[y=v[x][i]]) tarjan(y),cmin(low[x],low[y]);
        	else if(ins[y]) cmin(low[x],dfn[y]);
    if(dfn[x]==low[x]) {
        int y;
		scc++;
        do {
			y=st[tp--];
			ins[y]=0;
			bel[y]=scc;
			sz[scc]++;
		} while(y!=x);
    }
}

int main() {
	read(n);
	read(k);
	ans=k;
    for(int i=1; i<n; i++) {
    	int x,y;
    	read(x);
    	read(y);
        e[x].push_back(y);
		e[y].push_back(x);
    }
    dfs(1);
	memset(mn,0x3f,sizeof(mn));
    for(int i=1; i<=n; i++) {
		scanf("%d",&c[i]);
		cmin(mn[c[i]],dfn[i]);
	}
    for(int i=1; i<=n; i++)
		if(dfn[i]>rr[idfn[mn[c[i]]]])
			mn[c[i]]=0;
    for(int i=1; i<=n; i++)
		if(dfn[i]^mn[c[i]])
			v[c[i]].push_back(c[f[i]]);
    memset(dfn,0,sizeof(dfn));
	clk=0;
	for(int i=1; i<=k; i++)
		if(!dfn[i]) tarjan(i);
    for(int i=1; i<=k; i++)
		for(int j=0; j<v[i].size(); j++)
			if(bel[i]^bel[v[i][j]])
				ban[bel[i]]=1;
    for(int i=1; i<=scc; i++)
		if(!ban[i]) ans=MIN(ans,sz[i]);
    writeln(ans-1);
    return 0;
}

Compilation message (stderr)

capital_city.cpp:2: warning: ignoring '#pragma G ' [-Wunknown-pragmas]
    2 | #pragma G++ optimize(3,"Ofast","inline")
      | 
capital_city.cpp: In function 'void dfs(int)':
capital_city.cpp:65:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i=0,y; i<e[x].size(); i++)
      |                    ~^~~~~~~~~~~~
capital_city.cpp: In function 'void tarjan(int)':
capital_city.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=0,y; i<v[x].size(); i++)
      |                    ~^~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:117:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |   for(int j=0; j<v[i].size(); j++)
      |                ~^~~~~~~~~~~~
capital_city.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   scanf("%d",&c[i]);
      |   ~~~~~^~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59