Submission #76447

#	Time	Username	Problem	Language	Result	Execution time	Memory
76447		hamzqq9	Dijamant (COI16_dijament)	C++14	100 / 100	316 ms	18808 KiB

dijament

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 60000000000000000
#define MOD 1000000009
#define N 3005
#define MAX 5032117	
#define LOG 30
#define KOK 333
#define dec ewfewf
using namespace std;

int dec[N],dif,n,huhu,ord[N],mark[N];
bool flag,vis[N],no[N];
vector<int> v[N],q[N];
map<string,int> MP;

void grs() {

	cout<<"greska\n";

}

void dfs(int node) {

	if(vis[node]) {

		flag=0;

		return ;

	}

	vis[node]=1;

	for(int to:v[node]) {

		dfs(to);

	}

}

void solve(int que) {

	int node=q[que][0];

	for(int i=1;i<sz(q[que]);i++) v[node].pb(q[que][i]);

	sort(all(v[node]),[](int x,int y){

		return ord[x]>ord[y];

	});

	memset(vis,0,sizeof(vis));
	memset(mark,0,sizeof(mark));
		
	flag=1;

	for(int i=0;i<sz(v[node]);i++) {

		int to=v[node][i];

		if(vis[to]) {

			mark[i]=1;

			continue ;

		}

		dfs(to);

		if(!flag) break ;

	}

	if(!flag) {

		dec[node]=0;

		v[node].clear();

		grs();

		return ;

	}

	vector<int> pos;

	for(int i=0;i<sz(v[node]);i++) {

		if(!mark[i]) pos.pb(v[node][i]);

	}

	v[node].clear();

	for(int i:pos) v[node].pb(i);

	ord[node]=++huhu;

	cout<<"ok\n";

}

int main() {

	//freopen("input.txt","r",stdin);

	ios_base::sync_with_stdio(0);

	cin.tie(0);cout.tie(0);

	cin>>n;

	for(int i=1;i<=n;i++) {

		string s;

		cin>>s;

		if(!MP[s]) MP[s]=++dif;

		q[i].pb(MP[s]);

		cin>>s;

		while(1) {

			string dad;

			cin>>dad;

			if(dad[0]==';') break ;

			if(!MP[dad]) {

				no[i]=1;

				continue ;

			}
			
			q[i].pb(MP[dad]);

		}

	}

	for(int i=1;i<=n;i++) {

		if(no[i]) {

			grs();

			continue ;

		}

		int adding=q[i][0];

		if(dec[adding]) {

			grs();

			continue ;

		}

		bool fail=0;

		dec[adding]=1;

		for(int j=1;j<sz(q[i]);j++) {

			if(!dec[q[i][j]]) {

				grs();

				fail=1;

				dec[adding]=0;

				break ;

			}

		}

		if(fail) continue ;

		solve(i);

	}

}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 29 / 29
• Subtask 4: 44 / 44