oj.uz

Submission #76447

# Submission time Handle Problem Language Result Execution time Memory
76447 2018-09-13T14:11:41 Z hamzqq9 Dijamant (COI16_dijament) C++14
100 / 100
 316 ms 18808 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 2 ms 636 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 4 ms 812 KB Output is correct
7 Correct 4 ms 828 KB Output is correct
8 Correct 2 ms 828 KB Output is correct
9 Correct 2 ms 828 KB Output is correct
10 Correct 2 ms 828 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 640 KB Output is correct
6 Correct 4 ms 812 KB Output is correct
7 Correct 4 ms 828 KB Output is correct
8 Correct 2 ms 828 KB Output is correct
9 Correct 2 ms 828 KB Output is correct
10 Correct 2 ms 828 KB Output is correct
11 Correct 2 ms 828 KB Output is correct
12 Correct 2 ms 828 KB Output is correct
13 Correct 2 ms 828 KB Output is correct
14 Correct 3 ms 828 KB Output is correct
15 Correct 4 ms 828 KB Output is correct
16 Correct 2 ms 828 KB Output is correct
17 Correct 2 ms 828 KB Output is correct
18 Correct 3 ms 832 KB Output is correct
19 Correct 3 ms 836 KB Output is correct
20 Correct 3 ms 896 KB Output is correct
21 Correct 3 ms 896 KB Output is correct
22 Correct 2 ms 896 KB Output is correct
23 Correct 3 ms 896 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 5976 KB Output is correct
2 Correct 316 ms 10772 KB Output is correct
3 Correct 300 ms 12096 KB Output is correct
4 Correct 4 ms 12096 KB Output is correct
5 Correct 4 ms 12096 KB Output is correct
6 Correct 8 ms 12096 KB Output is correct
7 Correct 16 ms 12096 KB Output is correct
8 Correct 28 ms 12096 KB Output is correct
9 Correct 29 ms 12096 KB Output is correct
10 Correct 9 ms 12096 KB Output is correct
11 Correct 9 ms 12096 KB Output is correct
12 Correct 244 ms 18808 KB Output is correct